Latest Google InterView Questions-1

1) Given an parentheses tree as a string form the tree again. Write a perfect code for the same to return a node pointer.
e.g. (1(2(3)(4))())

Output 1
-----
2 null
-----
3 4

2) Given a very long list of words, find the groups of anagrams in it. (satin & stain). Do not restrict solution to ASCII characters, you could have unigram codes as well. Code the function and write the test cases.

3)Find the minimum and maximum element in an array in least possible number of comparisons?

4)A river separates two banks, there are 3 men and 3 lions on one side that need to be taken across using a boat that can carry 2 entities at a time(irrespective of being a lion and man), subject to the condition that at no point can you have more number of lions than men on any bank, as then the lions would eat the man/men. Solve the puzzle. Then code it to make it a generic program that solves the puzzle for X men and Y lions.


5)Given an array of red, green and blue balls arrange them in groups of all red together, greens together and blue together. Do in a single scan of the array.

6)Merge two linked lists without using extra memory.

7)Given three strings A=“hello” B=“bye” C=“welcome” and the occurrences of each of them in a file as occur_A=[1 4 8 10] similarly for B and C, where “hello” occurs as the first, fourth, eighth and tenth word in the file, find the smalled snippet of words that contains all the three. Write a perfect code for the same. By perfection it is meant, shippable and with exception handling.

8)Find the first non-zero digit from the right in 100! (Factorial of hundred). Can an int store hundred factorial. What size of array should be sufficient to solve the above problem. Write a code for the same.

9)Discussion on heaps(all functions, makeheap, insert, delete, getmin/max and their orders)

10)Millions of queries hit a server, at any instant get the top twenty queries that are hitting the server. You are given a function that gets the frequency of a given query.