Google interview question: Throw 2 eggs on 100 storied building

Google interview question: Throw 2 eggs on 100 storied building, and decide which exact level and its above is going to break the egg.

Underlying fact: if the thrown egg is unbroken, actually you could grab it and reuse it!

Ravi and I spent sometime today discussing it, with different solutions.

1, binary search is optimal when you have lots of eggs and achieving log2(n) complexity, but it's not the best way for this condition : only 2 eggs.

2, linear scanning. Assume the 100 level building is segmented into sections length of x, then we have floor(100/x) sections. First, start from the x th level and throw the 1st egg, if it is not broken, then go up x levels. If it breaks, then going inside that section below, and start from the bottom of that section, linearly upward until the egg breaks.

The number of trials f(x) in worst case is written as

f(x) = floor(100/x) + x;

it's easy to see that the optimal f(x) happens when x = 10, and f(x) = 20.


Yet, it's good enough, but not the optimal solution for this problem!

3, notice that the above solution can be seen as "double linear" scanning, which is something we will attack in this improved version:

Instead of considering equal length sections, notice that what if we make unequal sections? furthermore, how about decreasing # of levels in each sections when going upwards? Also notice that at the beginning, we need to ( almost always) start from the lowest level, why not try to "skip" more at the bottom sections?

Denote "outside" as #trials trying to identify the sections, and "inside" as #trials trying to identify within that section, we have a tradeoff to make here:

"outside" + "inside" == constant

meaning that when you spent more trials on "outside", you should not spent too much trials on "inside", otherwise you are not likely to improve.

Here we go!

Assume we have :

(x) + (x-1) + (x-2) + ... + (1) <=100

where each ( ) is the section length.

solve for:
sum_i=1 ^ x {i}<=100, we could use google calculator to compute:

sqrt(201) = 14.1774469

so the bottom section length is around roughly 14, and the respective section lengths upwards are 13, 12, 11, ....,1.

Bingo! See the magic here?!

so the strategy is similar fashioned, first decide the "outside" section until the 1st egg breaks, then dive inside that below section, and linearly upwards, throw the 2nd egg...

e.g. when the 1st egg breaks at 14th level, we spend 1 trial to decide the "outside" section, then spend the 2nd egg starting throwing from 1st level. So the worst case here is when the level is 13th, then we have to use up 13+1 = 14 trials.

This one is actually the upperbound for our formulation! Remember that tradeoff ?

Therefore we've achieved the "egg salvation" google brainteaser !

Thanks for the show! :D