Optimization Puzzles

Read these first

1. 01Halving the Search Space

   Binary search is the purest example of a whole family of interview puzzles: any question you can answer with a single yes/no query should be attacked by cutting the space of possibilities in half, not by guessing.

2. 02The Egg-Drop Problem

   With two eggs and a 100-floor building, find the highest safe floor using as few drops as possible, the puzzle that teaches you to balance the cost of a bad early guess against the cost of testing too cautiously.

3. 03When Greedy Fails

   Making the locally best choice at every step works for some problems and quietly produces the wrong answer for others, the puzzle is learning to tell which is which before you commit to an approach out loud.

Then the rest

1. 04Cutting a Cake Fairly
2. 05Explore Versus Exploit
3. 06Finding the Median With Few Comparisons
4. 07Finding the Second-Best Player in Fewest Matches
5. 08Proving a Greedy Rule Optimal by Exchange
6. 09Scheduling to Fit the Most Jobs
7. 10Searching a Unimodal Function
8. 11Shortest-Job-First and Average Waiting Time
9. 12Stable Matching and Gale-Shapley