Google Test

1. Give an efficient algorithm to generate the numbers of the form 2^i x 3^j x 5^k x 7^l in ascending order given i,j,k,l >= 0 and are integers.

2. Given a 2^n x 2^n chessboard and an infinite number of L shaped tiles (of size 2x2) which may be rotated and placed, is it possible to tile the entire chessboard leaving just a single gap?

3. Find the minimum number of comparisons required to find the minimum and maximum element in the array of 20 elements.

4. Jack and his wife went to a party where four other married couples were present. When Jack asks everyone (including his wife) how many hands they shook. He gets all different answers. No person shakes hands with their partners.

How many hands did Jack's wife shake?

Here are few more questions asked by google:

http://www.divye.in/2010/12/google-interview-questions-and-google.html

Goldman + DB

1. I have a polynomial with positive integer coefficient. You can ask me question "what is the value of the polynomial at x".

What is the minimum number of questions required to find out the polynomial.

2. You toss a coin until you get n consecutive heads. What is the expected number of tosses?

3 A random walk is a sequence of numbers R(n) such that R(n)=R(n-1)+1 with probability half and R(n)=R(n-1) -1 with probability half. Equivalent consider a particle on number line. It can move to left or right with probability half. R(0)=0 i.e. particle starts at 0.

Let N_b be the first integer n such that R(n) = b i.e particle visited the integer b for the first time.

i) Find P(N_b < t).

(I don't remember the other parts. Somebody please post the rest).

4. You have a deck of cards from which you pick a card without replacement until an ace is picked(any of the four ace). Find the expected number of picks.