Classic interview problems

The problems that have been asked for decades, each under the name people actually say out loud. Most have a trap, and the trap is what the question is really testing.

28 problems

Transitivity of correlationThe two correlations you are handed do not pin the third one down, but they fence it into exactly [−1/50, 1], and that interval dips below zero. The fence falls out of a 3×3 determinant read as a quadratic in the unknown, and out of a picture: 0.7 is an angle of 45.573°, both stocks live on a cone of that half-angle around the index, and putting them on opposite sides opens 91.146° between them. Also here: why the real tipping point is ab ≥ 0 together with a² + b² ≥ 1 rather than "both above 0.707", why 0.9 and 0.5 force a positive answer while 0.9 and −0.9 allow −1, why standing on the floor costs a rank, and why three Bernoulli(0.5) indicators with the same two correlations are confined to [0.40, 1] instead.
The Kelly criterionThe fraction that maximises long-run growth is exactly the edge, 2p-1, which is 0.2 on this coin, and one derivative gets you there. Double it and the growth rate is -0.0024469 a flip, negative on a game that leans your way three hundred times in a row, and the crossing happens at 0.3894 rather than at 0.4. The article carries the exact median over 300 flips, 25 dollars to 10504.19 at the optimum and to 12.00 at double, the reason about 48 percent of overbettors still finish ahead anyway, and the place where the textbook approximation mean minus half the variance returns the opposite sign.
The broken stickTwo random breaks, three pieces, and three inequalities that collapse into one. The quarter falls out of a square with no integral at all, and the average longest piece, 11/18, explains why the answer feels too low but isn't.
The birthday problemThe reflex answer is around 180, half the calendar. The real threshold is 23, because a match needs a pair and 23 people carry 253 of them. The same reasoning puts the answer to "does anyone share MY birthday" at 253 people, eleven times the crowd, and the square-root threshold behind both is why a 64-bit random id collides after five billion draws rather than eighteen quintillion.
The 100 prisoners problemIndependent guessing gives the prisoners 7.9 x 10^-31. Following the slip you just found gives them 0.311828, and the gap is thirty orders of magnitude from a rule you can state in one sentence. The strategy never raises anyone's individual chance above one half; it only makes the failures coincide, which is the whole lesson.
The Monty Hall problemTwo doors left is not two equal doors: your first pick was frozen at 1/3 and the other 2/3 piled onto the single door still closed. The number is not a fact about doors, it is a fact about the host. Let him open a door at random instead, show the same goat, and switching is worth exactly 1/2.
Twelve coins, three weighingsTwenty-four possible answers against 3^3 = 27 outcome sequences leaves just enough room, and four against four splits those answers into exactly 8, 8 and 8. Six against six always tips, so it wastes the level outcome and leaves twelve answers for nine remaining sequences, which makes halving impossible rather than merely slow. The counting argument bounds outcome sequences rather than strategies, so it rules out every adaptive continuation at once, and the explicit schedule closes the positive half.
Two envelopes problemRequiring the fifty-fifty at every amount you could open forces the weights to satisfy f(x) = f(x/2)/2, whose only solutions are proportional to 1/x, and that integrates to infinity at both ends. Conditional on the pair, the swap gains the smaller amount or loses it with equal chance, which is zero and needs no assumption at all. The article carries a proper spread where the conditional answer is genuinely x/2, and the infinite-mean spread where swapping really is right at every observable amount.
The winner's curseAcceptance restricts the value to below your bid, where a uniform variable averages half of it, and doubling half your bid returns exactly your bid. The expected profit is therefore identically zero at every bid up to 100 and 100 minus b above it, so there is no optimal bid to find. With a general multiplier the profit is b squared times k minus 2, over 200, making doubling the exact break-even multiple, and the article shows a value distribution starting at 50 where the same bidder profits.
Water jug problemAdding fives and threes never reaches four, and that observation is correct. It is also about the wrong set, because a pour is a subtraction and the reachable amounts are the integer combinations rather than the natural ones. An exhaustive state-graph search proves six pours is minimal, and the four missing sums turn out to be the gaps of a numerical semigroup.
The counterfeit bagTaking one coin from each bag reads 9.9 ounces whichever bag is light, and the failure is blindness rather than imprecision. Loading i coins from bag i makes the dial an injective function of the culprit, at a cost of the tenth triangular number. A 45-coin variant is cheaper, and powers of two identify any subset of light bags from one reading.
Burning ropesHalving the length and timing the flame is not a biased estimator of half the time, it is unrelated to it: across four thousand random cords the midpoint method scattered from under fifteen seconds to over forty-five. Lighting both ends gives exactly thirty on every cord, by an argument that never evaluates the burn rate.
The gold bar paymentSeven pieces cost six cuts and the schedule pays correctly, so the six-cut answer breaks one constraint and nothing else. Because the worker can hand pieces back, the contract is on his holding rather than on the transfer, and the ledger turns out to be a three-bit counter. Brute force finds 1-2-4 is the only three-piece solution.
Towers of HanoiThirty-two rings really do take 136 years at a move a second, which is what makes doubling it to 272 so tempting. The exact ratio between the two cases factors as two to the thirty-two plus one, so the guess is short by more than four billion times. The article carries the lower bound the recursion alone does not give, and the 2-adic rule for which ring moves when.
Spider and flyUnfolding two faces into a 2 by 1 rectangle turns the walk into a straight segment of length root five, crossing the shared edge at half height. The reflex answer of one plus root two is the same one-parameter family evaluated at the end of that edge instead of its middle, so the trap and the answer are two points on one curve.
Water and wineThe pour back really was diluted, and the conclusion still does not follow: both jars finish at six cups, so whatever left one jar was replaced cup for cup by what arrived. That argument needs no fractions and survives terrible stirring, while the number 1.5 cups does not.
Three switches, one bulbSix pairings have to be separated by a single observation, and a light-only strategy always leaves at least two candidates standing. Warmth is a genuine third readable state, and three states handed to three bulbs give exactly six readings, one per pairing. The article carries the impossibility count and the four-switch case where the trick fails.
The hat puzzleOf the eight colour triples, seven are feasible from a pool of three blue hats and two red. The first silence removes one, the second removes two more, and all four survivors put a blue hat on the third man, which is what makes his answer a deduction rather than a lucky call. A pool sweep shows three blue and two red is the only small pool where the story can happen.
The fly between two trainsTwo riders twenty-five miles apart close at fifty miles an hour, so a forty mile an hour fly shuttling between them flies exactly twenty miles. The series of shuttle legs gives the same twenty, with a first leg of 100/7 and a round-trip ratio of 1/21, but no finite number of legs ever reaches it: after eighty legs the exact total is twenty minus about 2.6e-52. The general law is wD/(a+b), and it holds identically in the rider speeds rather than by luck at 20 and 30.
The jeep problemA driver who eats one apple per loaded mile delivers 833 of 3000 across a thousand miles, because the price of a mile is the ceiling of the stock over the truck's capacity: three apples, then two, then one. The continuous optimum is 2500/3, but rounding the switch point down to mile 333 leaves 2001 apples needing three passes and produces a fake 834. A lower bound on loaded traversals proves 833 optimal without a dynamic programme, and the free return legs are the clause that separates 833 from 533.
The truelYou hit one time in ten, your two opponents three and six, and you shoot first. Firing into the air is worth 965/4736 = 20.376%, which beats removing the strongest player by 0.195 percentage points, because a landed hit drops you into the duel you must enter second at 7/37 rather than first at 10/37. The article carries all three option values, the fixed points they solve, and the single Nash equilibrium that turns the usual assumption into a conclusion.
Mutilated chessboardCut two diagonally opposite corners off a chessboard and 62 = 2 x 31 stays true, yet nothing fits. Writing the colour of a square as the sign (-1)^(i+j) turns the argument into arithmetic: every domino sums to zero, the two lost corners both carried +1, and the board left over is 30 against 32. The converse, Gomory's theorem, is the harder half and it goes the other way.
South, east, north — back where you startedThe North Pole really is a solution, so the trap is only the words "and nowhere else". A mile north of the parallel whose whole lap measures 1/n of a mile, the eastward mile is n exact revolutions, which puts a starting circle 1.159 miles from the South Pole for one lap, 1.080 for two, 1.053 for three. Every point of every circle works, so the honest count is uncountable rather than infinite.
Snail climbing a poleThree feet up each day, one foot back each night, ten feet to climb. Dividing ten by the net two feet a day gives five days, and it charges the snail for a night it never spends. The dawn heights settle the day, the last climb settles the moment, and the closed form the video had no room to voice is a single ceiling function.
Russian rouletteSix slots in a ring, two of them marked side by side. You land on a blank one and get one move: step forward, or draw a fresh slot at random. Both look like two in six. Stepping is one in four, drawing again is one in three, and the whole gap comes from the fact that the two marks are touching. Pull them apart and the advice reverses.
False positive paradoxA disease one person in two hundred carries, and a test with no false negatives at all. The reflex answer to a positive result is above ninety percent, and it is wrong by more than a factor of ten. A crowd of a thousand people shows why before the algebra does, and Bayes puts the exact figure at 100/1493.
Coin weighingA counterfeit coin that might be heavy or light, a balance that only reports which side falls, and a hundred dollars a weighing. Counting rules out four; only a construction gets you five.
Boy or girl paradoxTold that one of two children is a girl, the chance both are girls is 1/3. Watch a girl open the door instead and it is 1/2, from the same four families and the same prior. One likelihood separates them: a mixed family always satisfies the statement, but sends the girl to the door only half the time. Push the identifying detail to a girl born on a Tuesday and the answer slides to 13/27.