Google And The Puzzle of Dropping EggsBy Angsuman Chakraborty, Gaea News Network
Saturday, June 10, 2006
Google is also known for its interesting interview questions. Enjoy this one and my solution. Suppose you have two eggs. These are special eggs—they can take much more punishment than you average chicken egg. The question is exactly just how much punishment can they take?
Using a 100 storey building and only the two eggs, how would you find out which is the highest floor of the building you can drop the eggs from, before they break?
It could be the 1st floor but it could also be the 99th floor—you don’t know but to test, you need to try dropping the eggs from different floors and see what happens.
Are you done yet? My solution is simple.
Use binary search with one egg till it breaks. Use linear search with the second egg till it breaks. And you have the solution. If that’s not clear enough allow me to explain.
First drop one egg from 50th (midway).
- If it breaks (no more binary search) then drop the second egg from first floor. Move up one floor at a time till it breaks.
- If it doesn’t break then drop it from 75th floor.
- If it breaks then drop the second egg from 76th floor. Move up one floor at a time till it breaks.
- If it doesn’t break then drop it from the 87th floor…
I hope you get the picture by now. I would love to see anyone coming with a better optimized solution.
Update: The optimization is to minimize the number of drops.