CareerCup

Instead of taking equal intervals, we can increase the number of floors by one less than the previous increment.
For example, let’s first try at floor 14. If it breaks, then we need 13 more tries to find the solution. If it doesn’t break, then we should try floor 27 (14 + 13). If it breaks, we need 12 more tries to find the solution. So the initial 2 tries plus the additional 12 tries would still be 14 tries in total. If it doesn’t break, we can try 39 (27 + 12) and so on. Using 14 as the initial floor, we can reach up to floor 105 (14 + 13 + 12 + … + 1) before we need more than 14 tries. Since we only need to cover 100 floors, 14 tries is sufficient to find the solution.

Therefore, 14 is the least number of tries to find out the solution.

Given N find value of K such that K + (K-1) + (K-2) ..... + 1 = N or least K such that sum is just above N for eg if N = 100 ans will be 14 because 14 + 13 + 12 .... + 1 = 105

In fact, not only 2 eggs, m eggs can be solved by dynamic programming.

let there be N story building

Throw first egg from Xth Floor
if (egg does not break)
then throw egg from (2X)th Floor
continue it up to egg does not break
if egg breaks at i*Xth Floor
the strength of eggs is between {(i-1)*X + 1}th to {i*X - 1} floor
**********MAX N/X iteration
now take 2nd egg and throw it one by one until it break
**********Max X-2 itration

total MAX iteration T = N/X + X-2 ---------(1)

USE
dT/dX=0; ------------MAXIMA AND MINIMA


dT/dX= -N/(X^2) + 1 = 0
X = N^.5


so total no of iteration = 2(N^.5) - 2

Optimal solution is O(sqrt(N))
You can find it by searching for "Google Interview Puzzle : 2 Egg Problem"

Its a 2 lists skip list with sqrt(n) items in first list at an interval of sqrt(n) items in second list