Google Eggs – Puzzles, Answers and Comments
Came across the Google Egg Problem, which essentially says: Given n floors and m eggs, what is the approach to find the highest floor from which eggs can be thrown safely, while minimizing the throws (not broken eggs). While the solution presented in the post is not generic (considers 2 eggs), what I found most interesting was an answer by “Brandon”:
This entire “puzzle” is based on an assumption that an egg really can survive a 100 story drop. Personally I have never seen an egg fall more than about 8″ without breaking so this is a theoretical, hypothetical question with no factual basis. Both eggs could break after the 1st drop from the 1st floor which means your whole experiment is screwed.
Well said Brandon! That kind of sense of humor is worth more than a dynamic programming solution I was working on silently.
But for the readers for whom humor will not suffice, here is a link to the original problem, at least the most original link I know. The recursive formulation kind of goes like:
Let f(n,m) be the minimum number of attempts given n floors and m eggs. There is no guarantee that we will still have the egg intact after the test.
Then, f(n,1) = n // We have no option but to climb floors one by one.
Similarly, f(1,m) = 1 // We just need one try if there is only one floor
The recursion is built around the first action – which floor do we try the first egg from. If that is j, and if the egg breaks, then we have j-1 floors left, m-1 eggs left. If the egg doesn’t break, then we have n-j floors and m eggs left. Then the recursion we get is:
This leads to a straightforward dynamic programming formulation, which has mn entries in the DP table and each entry can be computed in at most m time, Therefore, the algorithm runs in O(n m^2) time. Here are some sample results – the Java source code is here.
100 floors, 2 eggs. Optimal number of attempts: 14 [Try first egg at floor # 9] [This matches the result given here, but the floor number for first egg attempt is not the same.]
200 floors, 3 eggs. Optimal number of attempts: 11 [Try first egg at floor # 25]
400 floors, 5 eggs. Optimal number of attempts: 10 [Try first egg at floor # 19]
1000 floors, 3 eggs. Optimal number of attempts: 19 [Try first egg at floor # 13]
1000 floors, 4 eggs. Optimal number of attempts: 13 [Try first egg at floor # 207]
1000 floors, 5 eggs. Optimal number of attempts: 11 [Try first egg at floor # 363]
1000 floors, 20 eggs. Optimal number of attempts: 10 [Try first egg at floor # 489]
1000 floors, 30 eggs. Optimal number of attempts: 10 [Try first egg at floor # 489]
Update 1: My first version of this post had a fatal flaw in it – a plus instead of a comma. Catastrophic result, but problem wasn’t just a typo – problem was in approaching the recursion from a divide and conquer perspective, rather than a “first action” perspective.
Update 2: Nikita Rybak mentions that he has an O(n log n) solution. If I find it, I will link it to the solution. (Nikita: If you find it, can you put it up on your website?)
Update 3: Logical next question – what is the closed form expression of f(n,m)?