Two eggs, one hundred floors.
The two-egg drop puzzle: find the highest safe floor of a 100-storey building while breaking at most two eggs, in the fewest worst-case drops. Binary search fails you here, and the fix teaches a lesson about balancing worst cases that shows up all over algorithm design.
A building has 100 floors. There is a critical floor F, between 0 and 100: an egg dropped from floor F or below survives, and an egg dropped from any floor above F breaks. All eggs are identical, and a surviving egg is undamaged and fully reusable.
You have exactly two eggs. Once both are broken, you can learn nothing more.
Devise a strategy that identifies F exactly, and minimises the number of drops in the worst case. How many drops does it need?
The tempting first answer is binary search: drop from floor 50. But if that egg breaks, you hold one egg and 49 candidate floors, and a single egg permits no gambles. You must walk floors 1, 2, 3, ... one at a time from the bottom of the range, because skipping any floor and breaking would leave F ambiguous forever. So binary search's worst case is 1 + 49 = 50 drops, barely better than never having had a second egg at all.
At the other extreme, pure linear search from floor 1 never risks ambiguity but needs 100 drops in the worst case. The right strategy sits between these poles, and the way to find it is to ask a precise question: if my answer is "d drops always suffice", what is the largest building that claim can cover?
Stuck? Open hints one at a time
Each hint gives away one more layer. Stop the moment something clicks.
Hint 1 a nudge
Suppose your first drop is from floor k and the egg breaks. You now need up to k - 1 sequential drops. So a budget of d total drops means the first drop can be no higher than floor d. Where can the second first-egg drop go?
Hint 2 the key move
Each time the first egg survives, you have spent a drop, so the remaining budget shrinks by one, and your next jump must shrink by one floor too: first jump d, then d - 1, then d - 2. Every failure branch then costs exactly d drops total. Balance is the whole idea.
Hint 3 nearly the answer
With budget d you can cover d + (d - 1) + ... + 2 + 1 = d(d + 1)/2 floors. Find the smallest d with d(d + 1)/2 at least 100.
The solution
Reveal the full solution
Fourteen drops suffice, and thirteen do not.
Drop the first egg from floor 14. If it survives, climb 13 floors to 27, then 12 to 39, then 11, 10, and so on: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, and finally 100. Whenever the first egg breaks, walk the second egg up one floor at a time through the gap below the break, starting just above the last floor the first egg survived.
The design principle is worst-case balancing. Every drop that survives spends one unit of budget, so the next gap must be one floor smaller to keep the total constant. Break at 14: 1 drop spent, at most 13 sequential drops remain, total 14. Survive to 27 and break there: 2 spent, at most 12 remain, total 14 again. Every branch of the strategy tree costs at most 14. A fixed-gap strategy cannot do this; jumping by a constant g costs more in the late branches than the early ones, and the worst branch is what you are graded on.
The lower bound comes from a coverage argument. With a budget of d drops, the first drop cannot exceed floor d (a break above that leaves too many floors for one egg), the second cannot exceed d - 1 above the first, and so on. The most floors any two-egg strategy can distinguish in d drops is therefore d + (d - 1) + ... + 1 = d(d + 1)/2. Since 13 x 14 / 2 = 91 is short of 100 and 14 x 15 / 2 = 105 clears it, d = 14 is optimal. The general answer scales as the square root of the number of floors, a complexity class you rarely meet elsewhere.
What this puzzle is really testing
Whether you notice that the cost model changed. Binary search is optimal when every probe costs the same regardless of outcome; here a "break" outcome is catastrophically more expensive than a "survive", and the optimal strategy deforms from halving into a decreasing-stride ladder. The underlying discipline, choosing probes so that all worst cases cost the same, is the same one behind binary search on the answer, and the k-egg generalisation is a textbook dynamic programming recurrence: with e eggs and d drops you cover f(e, d) = f(e - 1, d - 1) + f(e, d - 1) + 1 floors.
Follow-ups to expect
Three eggs and 1000 floors (the recurrence answers it: 19 drops). Minimising the average number of drops instead of the worst case, which changes the optimal first floor. And the sharpest one: why does the two-egg answer grow as the square root of n while one egg is linear and unlimited eggs are logarithmic? Being able to say where each regime comes from is worth more in an interview than the number 14.