Tower of Hanoi, 64 disks.
The Tower of Hanoi puzzle: move 64 disks between three pegs, one at a time, never placing a larger disk on a smaller one. How many moves does it take, and why is the answer 2 to the 64 minus 1? The recurrence behind it is the template for every divide-and-conquer count.
Three pegs. On the first sit 64 disks of different sizes, largest at the bottom, smallest on top. You may move one disk at a time, taking the top disk of any peg and placing it on another peg, and you may never place a disk on top of a smaller one.
What is the minimum number of moves needed to transfer the whole tower to another peg? Then give a strategy that achieves it.
The legend says monks in a temple are performing this task with 64 golden disks, and the world ends when they finish. Before working out whether to worry, try the small cases: one disk takes one move, two disks take three, three disks take seven. The pattern is visible, but the interview wants the argument that the pattern continues, and that no cleverer strategy beats it. Ask what must happen to the largest disk at some point in any solution.
Stuck? Open hints one at a time
Each hint gives away one more layer. Stop the moment something clicks.
Hint 1 a nudge
To move the largest disk, every other disk must be stacked on the one peg that is neither its source nor its destination. Moving those 63 disks there is a smaller instance of the same problem.
Hint 2 the key move
Let T(n) be the minimum moves for n disks. Move n minus 1 disks aside, move the big one, move n minus 1 disks back on top: T(n) equals 2 T(n minus 1) plus 1, with T(1) equal to 1. Unroll it.
The solution
Reveal the full solution
2 to the power 64, minus 1: 18,446,744,073,709,551,615 moves. At one move per second that is about 585 billion years, so the monks are not a concern.
The strategy for n disks: move the top n minus 1 disks to the spare peg, move the largest disk to the destination, then move the n minus 1 disks from the spare peg onto it. Each of the two sub-moves is the same problem with one fewer disk, so the count satisfies T(n) equals 2 T(n minus 1) plus 1 with T(1) equal to 1. Unrolling: T(2) is 3, T(3) is 7, T(4) is 15, and in general T(n) is 2 to the power n minus 1, which you can confirm by substituting it back into the recurrence: 2 times (2 to the power (n minus 1) minus 1) plus 1 equals 2 to the power n minus 1.
That the strategy is optimal takes one more sentence. In any solution, the largest disk must move at least once, and at the moment of its first move the other n minus 1 disks must all be on the single remaining peg, which took at least T(n minus 1) moves to arrange; after the largest disk's last move, those disks must be moved onto it, another T(n minus 1) at least. So every solution uses at least 2 T(n minus 1) plus 1 moves, which is exactly what the strategy uses. Recurrence and lower bound coincide, so the answer is exact.
What this puzzle is really testing
Whether you can turn "solve it for n" into "solve it for n minus 1, twice, plus something", and then reason about the recurrence rather than the moves. The same recurrence shape, two half-size subproblems plus work to combine, governs merge sort and every divide-and-conquer algorithm; the difference is that merge sort's "plus" is linear and its depth is log n, giving n log n, while Hanoi's subproblems shrink by only one disk, giving depth n and exponential total. The log n versus n log n essay walks through why the shrink rate is everything. Writing the recursive solution and proving it by induction is the exercise in recursion as induction, and Hanoi is its canonical example.
Follow-ups to expect
Write the move sequence iteratively: on odd moves shift the smallest disk one peg cyclically, on even moves make the only legal move not involving it. Four pegs instead of three, where the optimal count drops dramatically and the exact formula was only proven in 2014. And the question that checks understanding: which disk moves on move number k? The answer is the position of the lowest set bit of k, which links the puzzle to binary counting.