## Welcome Guest

### Questions for Google

Rate the Questions

Rating: 2.7/5

 Q. No. : 1 Question : Implement merge sort of linked list? Solution Discuss
 Q. No. : 2 Question : You need to organize a football tournament. There are n teams given. You need to prepare a schedule for the matches so that each team plays with every other team and on the same day no team plays twice. You want to finish the tournament as early as possible.Give schedule for tournament. Solution Discuss
 Q. No. : 3 Question : Find the Nth largest node in a BST? Solution Discuss
 Q. No. : 4 Question : If you were designing a web crawler, how would you avoid getting into infinite loops? Solution Discuss
 Q. No. : 5 Question : How do you detect the duplicate documents? Consider you have over million urls. Solution Discuss
 Q. No. : 6 Question : You are given 2 eggs. * You have access to a 100-storey building. * Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical. * You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking. * Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process Solution Discuss
 Q. No. : 7 Question : Write code to compare two arrays if they contain the same elements Solution Discuss
 Q. No. : 8 Question : How to implement a queue using one integer. this should store value 0 to 9. example suppose queue has first value 2 then insert 4 then 6 so it should look like 246. first value should be popped as 2. then it should be 46. program should support 0 in all the levels also. example queue should handle like 01235 also, 0 as first value in queue. remember 0 just to use integer, nothing else as data storage. Solution Discuss
 Q. No. : 9 Question : You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number? Solution Discuss
 Q. No. : 10 Question : Find the next in order node of given node in binary tree. Write the program of same. pointer to parent node is given. Solution Discuss
 Q. No. : 11 Question : How to design the netflix movie recommendation algorithm? Discuss
 Q. No. : 12 Question : Pretend there is a robot that has to navigate a maze (N x M). The robot can only move down or right and the maze can contain walls. Write an algorithm to determine the number of paths the robot can take. Solution Discuss
 Q. No. : 13 Question : Efficiently implement 3 stacks in a single array. Solution Discuss
 Q. No. : 14 Question : Count number of bits and do it in O(1) Solution Discuss
 Q. No. : 15 Question : Write the code for a change vending machine. Solution Discuss
 Q. No. : 16 Question : You have to make 125 packets of sugar with first one weighing 1 kg, second 2 kg, third 3 kg etc ...and 125th one weighing 125kg.You can only use one pan of the common balance for measurement for weighing sugar, the other pan had to be used for weights i.e. weights should be used for each weighing. It has come into notice that moving weights into and out of the pan of the balance takes time and this time depends on the number on the number of weights that are moved. For example - If we need to measure 4 kg using weights 1 and 3 only, it will take twice as much time needed to measure 1 kg. Lets say we want to make sugar packets of weights 1,3,4 using weights 1 and 3 only. For this first we measure 1 kg, with 1 unit of time, we place 3 kg along with 1 kg and measure 4kg with again 1 unit of time, and finally we move 1kg out of pan to measure 3kg in 1 unit of time. So in 3 units of time we could measure 1,3 and 4kg using weights 1 and 3 only. Now you have to make sugar packets of all weights from 1 to 125 in minimum time, in other words in minimum movement of weights. The question here is to find out the minimum number of weighs needed and the weight of each the weights used and the strategy to be followed for the creation of 125 packets of sugar. Solution Discuss
 Q. No. : 17 Question : Write a program to shuffle an pack of cards in the most efficient way. Solution Discuss
 Q. No. : 18 Question : Given an array of integers(both positive and negative) divide the array into two parts(sub-arrays) such that the difference between the sum of elements in each array is minimum? Solution Discuss
 Q. No. : 19 Question : Sort an array of 0s, 1s and 2s in O(n) time and O(1) space. Solution Discuss
 Q. No. : 20 Question : You are given 2 arrays of size ‘n’ each. You need to stable-merge these arrays such that in the new array sum of product of consecutive elements is maximized and the relative ordering of elements of A and B in C is not reversed. eg A= { 2, 1, 3} B= { 3, 7, 9} Stable merging A and B will give an array C with ’2n’ elements say C={c1, c2, c3, c4, c5, c6} You need to find a new array C by merging (stable) A and B such that sum= c1*c2 + c3*c4 + c5* c6….. n terms is maximum. Solution Discuss
 Q. No. : 21 Question : Given a document and a query of K words, how do u find the smallest window that covers all the words at least once in that document? (given you know the inverted lists of all K words, that is, for each word, you have a list of all its occurrrences). This one is really hard. Could someone propose an algorithm in O(n)? Solution Discuss
 Q. No. : 22 Question : Find the median of 2 sorted arrays Solution Discuss
 Q. No. : 23 Question : You are given an array of N integers. Your job is to find maximum and second maximum element in N+logN comparisons. Solution Discuss
 Q. No. : 24 Question : Given two character arrays, find the common characters. eg A[] = {'a', 'x', 'y', 'z'} B[] = {'l', 'z', 'a', 'm', 'n'} Output: {'a', 'z'} Solution Discuss
 Q. No. : 25 Question : Given a source array of integers with possible duplicates and a target integer, write algorithm to find out 2 numbers in source array whose sum is equal to target If pre-processing of source in the above is allowed, what pre-processing will you do to reduce the complexity of algorithm written above ? Solution Discuss
 Q. No. : 26 Question : You are given 2 arrays sorted in decreasing order of size m and n respectively. Input: a number k <= n*n and >= 1 Output: the kth largest sum(a+b) possible. where a (any element from array 1) b (any element from array 2) Solution Discuss
 Q. No. : 27 Question : we are given N blocks of height 1…N. In how many ways can we arrange these blocks in a row such that when viewed from left we can see only L blocks (rest are hidden by taller blocks) and when seen from right we see only R blocks? for N=3, L=2, R=2 there are two ways 1, 3, 2 and 2, 3, 1. Solution Discuss
 Q. No. : 28 Question : Given an array, remove all the 'a's and add one 'd' after each 'b', do it in O(n) Solution Discuss
 Q. No. : 29 Question : Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure. Solution Discuss
 Q. No. : 30 Question : Given a Binary Tree, Programmatically you need to Prove it is a Binary Search Tree Solution Discuss
 Q. No. : 31 Question : How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points ? Solution Discuss
 Q. No. : 32 Question : Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 ... iN c1 c2 c3 ... cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 ... in cn Solution Discuss
 Q. No. : 33 Question : Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M >> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm Solution Discuss
 Q. No. : 34 Question : There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random. Hint: 1. Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2. It should be done in O(n). Solution Discuss