Here is a list of 10 puzzles which have been asked on a Google Interview. They are not in any specific order.
Reverse a Linked-list. Write code in C. Answer
Challenge – Equal Probability between 1 and 7
Write a method to generate a random number between 1 and 7, given a method that generates a random number between 1 and 5. Answer
Sub-Array with the Largest Sum
You are given an array with integers (both positive and negative) in any random order. Find the sub-array with the largest sum. Answer
You have two identical eggs. Standing in front of a 100 floor building, you wonder what is the maximum number of floors from which the egg can be dropped without breaking it. What is the minimum number of tries needed to find out the solution? Answer
Four People on a Rickety Bridge
Four people need to cross a rickety bridge at night. Unfortunately, they have only one torch and the bridge is too dangerous to cross without one. The bridge is only strong enough to support two people at a time. Not all people take the same time to cross the bridge. Times for each person: 1 min, 2 mins, 7 mins and 10 mins. What is the shortest time needed for all four of them to cross the bridge? Answer
In a country where everyone wants a boy, each family continues having babies till they have a boy. After some time, what is the proportion of boys to girls in the country? (Assuming probability of having a boy or a girl is the same) Answer
Probability of a Car Passing By
The probability of a car passing a certain intersection in a 20 minute windows is 0.9. What is the probability of a car passing the intersection in a 5 minute window? (Assuming a constant probability throughout) Answer
You have a stream of bytes from which you can read one byte at a time. You only have enough space to store one byte. After processing those bytes, you have to return a random byte. Note: The probability of picking any one of those bytes should be equal. Answer
How would you cut a rectangular cake into two equal pieces when a rectangular piece has already been cut out of it? The cut piece can be of any size and orientation. You are only allowed to make one straight cut. Answer
Two old friends, Jack and Bill, meet after a long time.
Jack: Hey, how are you man?
Bill: Not bad, got married and I have three kids now.
Jack: That’s awesome. How old are they?
Bill: The product of their ages is 72 and the sum of their ages is the same as your birth date.
Jack: Cool… But I still don’t know.
Bill: My eldest kid just started taking piano lessons.
Jack: Oh now I get it.
How old are Bill’s kids? Answer
How many can you answer in the first attempt? Post in comments.
Feel free to add to this list or leave a comment. Please tweet, Digg or Stumble.
If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:
I have noticed you don’t monetize your website, don’t waste your
traffic, you can earn additional cash every month because you’ve got high quality content.
If you want to know how to make extra bucks, search for: Boorfe’s tips best adsense
alternative
Can we solve first question in Java as well ?
Whether you get the job you want really depends on your answers during the interview, even so during this economic crisis!
@ Josh- dude u r wrong about the egg problem. u r saying that Start at 50, if it breaks, go to 25, otherwise 75. If at 25 and it breaks, go to 13. How will u go to 13 if ur second egg already broke on the 25th floor. U have only 2 eggs. The optimum value of no. of tries is 14 , u can’t reduce it any more..:)
These puzzles are quite interesting!!!!!!!!!
Even an Ostrich egg, one of the hardest and largest currently on the planet, would crack at a fall of more than 3-4 ft. So the answer is Floor 1. Part of business is deciding what questions matter and which don’t. These types of questions test whether employees can have fun together, not solve real world problems together. I suggest both Google and Microsoft look at the management consulting firm questions which are equally complex but based in reality. For example, a copper mining company does $300M in one year, and the next year is doen $50M. What is the strategy for recovering that lost revenue? The other example is the two buckets – my answer is just 5 steps and call legal counsel. 1. Fill the 5gal buget; 2. Pour 3 gals into the second bucket and you have 2 gals remaining in the first bucket, you are half way done having measured two gals; 3. Throw out the water from both buckets; 4. Fill the 5 gal bucket again; 5 empty into the 3 gal bucket and again you are left with 2 gals in the first bucket. You have now measured 4 gals. No one said anything about retaining the water, only that you ‘measure’ 4 gals – call legal and they will concur. THAT is a practical, more efficient solution that any person engaged in business is in fact higly likely to deal with, the parsing of legal language to come to the most efficient solution to a problem.
Josh – you only have 2 eggs. If you break them both, then you have nothing else to drop.
Chester – 3,4,6 is the only triple that multiplies to 72 and adds to 13, so Jack would have known the ages before hearing about the piano lessons. He didn’t, so that doesn’t work.
However, the piano question isn’t quite right. It is possible that the kids are 2, 6, and 6, but the 6-year-olds were born, say, 11 months apart, and the older 6-year-old has just started piano.
Regarding how many children question,
there is also 3,4,6
as 3*4*6 = 72, 3+4+6 = 13
Children usually start learning piano around 6. I think this is better than
3,3,8, which implies the eldest start piano at 8 years old and he has a twin kids (3,3).
For the eggs problem, how is it not a better solution to just divide the interval?
Start at 50, if it breaks, go to 25, otherwise 75. If at 25 and it breaks, go to 13, otherwise 38, and so on. Maximum should be:
50, 25, 13, 7, 4, 2, 1…. so 7 tries
50, 25, 38, 32, 28, 26, 27
Hi
Nice post , all are great tricky questions and can increase our mind and make it sharp . and help in our interviews.
Regards, Anup Kanwar
Because Jack’s Birth date is 14th… not 15th!!
I hope you get it!! 🙂
Thanks
The answer to the cheating husbands is wrong. It states that “…The 1 remaining woman, who is being cheated on, would have assumed there are no cheaters…” However, they are all being cheated on, and as the mayor did not specify who was the ‘cheater’ the status quo remains unchanged. All women know about everyone’s husband except their own, i.e. they are all aware of 99 cheaters- saying that there is definitely a cheater, would in no way cause one woman to assume that there are no cheaters, as the answer states.
Neha, if they were 9,4,2 the sum would be unique (15) and Jack would have found out. He got confused because there was a tie.
Why not 9,4,2 for the kids age?
OMG I was asked the question about piece of cake when I was in 6th grade 🙂
you drow a line that goes on centers of both rectangles.
he couldn’t make decision, therefore there must be at least two combinations which add up to his birth date
so if you list all the possible cases you’ll see that there are
2+6+6=14
3+3+8=14
then he mentioned eldest kid so answer is 3 3 8, because there is no eldest kid in 2 6 6.
Great post. Thanks!
Awesome post. Thanks!
Hi Amol, Thanks for pointing that out. I have added all the options. 12, 6, 1. The sum is 19 not 13 so there will not be a conflict in that case.
For the question “How old are my children”, arent a lot of possibilities neglected? eg – Why arent there any children with age 1?
9, 8, 1
24, 3, 1
18, 4, 1
36, 2, 1
12, 6, 1
In this case, in addition to the two cases which add up to 14 (as pointed out in the solution), there is another case wherein the ages add up to 13:
12, 6, 1 (sum=13)
6, 4, 3 (sum=13)
Why is this case ignored? Isnt more data required to “break the tie” and get a unique solution?
i knew 4 of them already (cheating, pirates, bridge and children age) the others the only one i didnt got at the first try was the eggs problem optimal solution.
The Boys and Girls question reminds me of people who think they have a roulette system. No matter when you stop or start, you can’t get around the fact that each individual roulette bet is a losing one, and these couples can’t get around the fact that each individual birth is 50/50.