Back to Interview Games
Egg Drop Problem
CombinatorialHard
30 min
50 pts
Description
Minimize worst-case drops to find critical floor in n-story building with k eggs.
Game Rules
You have k eggs and an n-story building. Find the highest floor from which an egg can be dropped without breaking. What is the minimum number of drops needed in the worst case?
Examples
With 2 eggs and 100 floors: Use binary search strategy
Start at floor 50, then adjust based on result
Optimal strategy uses dynamic programming
Hints
Think about binary search
Consider worst-case scenarios
Solution (Click to reveal)
Use dynamic programming: f(k, n) = min(max(f(k-1, x-1), f(k, n-x)) + 1) for x in [1, n]. For 2 eggs and 100 floors, answer is 14 drops.