Related InterviewSolutions

• A set X can be represented by an array x[n] as follows:Consider the following algorithm in which x,y and z are Boolean arrays of size n:algorithm zzz(x[] , y[], z []){int i;for (i=O; i<n; ++i)z[i] = (x[i] ^ ~y[i]) V (~x[i] ^ y[i])}The set Z computed by the algorithm is:(A) (X Intersection Y)(B) (X Union Y)(C) (X-Y) Intersection (Y-X)(D) (X-Y) Union (Y-X)
• An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array (GATE CS 2006)(A) Solves it in linear time using a left to right pass of the array(B) Solves it in linear time using a right to left pass of the array(C) Solves it using divide and conquer in time 8(nlogn)(D) Solves it in time 8(n2)
• The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is(A) (n)(B) (logn)(C) (log*n)(D) (n)(A) A(B) B(C) C(D) D
• In a village, people build houses in the same side of the road. A thief plans to loot the village. He wants maximum amount of money without having any risk of getting caught. By some means, the villagers know that their adjacent house is being looted or not and thus they become alert. So the thief cannot loot contiguous two houses. Given that the thief knows the amount of money stored in each house and the road is straight and there is no turning, which is the most efficient algorithmic strategy to solve this problem?(A) Brute-force(B) Dynamic Programming(C) Backtracking(D) Divide and Conquer
• In a complete k-ary tree, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is: (GATE CS 2005)(A) nk(B) (n – 1) k+ 1(C) n( k – 1) + 1(D) n( k – 1)
• Which of the following is not an in-place algorithm?(A) Insertion sort(B) Selection sort(C) Merge sort(D) Heap sort
• Given 8 identical coins out of which one coin is heavy and a pan balance. How many minimum number of measurements are needed to find the heavy coin?(A) 2(B) 3(C) 4(D) 7