Eggs and Building Puzzle-Asked in Nvidia and Google interviews.
Question:
There is a building of 100 floors
If an egg drops from the Nth floor or above it will break. If it’s dropped from any floor below, it will not break. You’re given 2 eggs. Find N, while minimizing the number of drops for the worst case.
These are very strong eggs, because they can be dropped multiple times without breaking as long as they are dropped from floors below their “threshold” floor, floor N. But once an egg is dropped from a floor above it’s threshold floor, it will break.
Solution: 14th floor
Try to drop the egg from the xth floor then 2xth floor till 100th, in this case, the worst-case time will be (100/x)+(x-1). The worst case will be when Egg #1 breaks at the 100th floor then we have to try Egg #2 from (100-x)th to 99th floors. In (100/x) + (x-1) equation, with increase in x, 100/x decreases while (x-1) increases, thus we can minimize it when 100/x = (x-1), this gives x ~10, which gives worst-case number as 19 drops.But increasing the floor every time by x is not a very nice idea, as, with each new increase in Egg #1 drop, we should decrease Egg #2 drops to minimize the worst-case number. so if we drop Egg #1 from xth floor initially, then in the next turn we should try x + (x-1)th floor(to keep the worst-case number same).
Thus we can say X + (x-1) + (x-2)…1 = 100
X(X+1)/2 = 100 => X=14.So we should drop Egg #1 from 14th, then 27th, then 39th, and so on.
