How to pass interviews with puzzles

"They'll give me a puzzle. What if I don't know the answer?"

An interview puzzle is not an exam with the answer at the back of the book. The interviewer has ten minutes to see how you think and write it down. The answer matters, but it is just one line in their notes.

Are puzzles asked at all? It depends on where you're going. Big tech companies have mostly dropped brainteasers: in 2013 Laszlo Bock, then Google's head of people operations, told the New York Times that their own data showed brainteasers did nothing for hiring. But at quant firms and trading houses, probability and logic puzzles are still a normal part of the interview, consulting asks for rough estimates, and software and analytics interviews ask algorithm and probability questions that are easy to mistake for a brainteaser.

• Think out loud from the first minute: silence is something the interviewer can't write down.
• If you know the puzzle, say so, then explain the solution as if you were deriving it for the first time.
• Find out in advance what kind of puzzles your target employer asks: quant, consulting and software ask very different things.

"The answer is obvious. Why is the interviewer smiling?"

The most common interview mistake is not hard maths but a quick answer to a different question than the one asked. The brain slips in a familiar template, and out comes a confident but wrong number.

The other half of reading the question is asking the interviewer. Many classic puzzles change their answer because of one easily missed detail. Here is the Monty Hall problem. Tap the underlined words: each is an assumption worth saying out loud.

• Restate the question in your own words before solving: the interviewer will hear at once if you understood it differently.
• Say your assumptions out loud: "I'm assuming the host always opens a door with a goat, right?"
• Plug the answer back into the question. It's the cheapest check there is.

Deeper: the classic version of the notebook puzzle, and the Monty Hall problem, with a game and a simulation.

"A hundred people, a hundred steps. How do you even hold that in your head?"

Big numbers in a question are often only there to scare you. If you can't see the puzzle at once, solve it for 1, 2, 3, 4 and look at the answers. A pattern usually shows by the fifth step, and explaining it is easier than guessing it.

Why squares? Locker 12 is touched by students 1, 2, 3, 4, 6 and 12, its divisors. Divisors come in pairs: 1 and 12, 2 and 6, 3 and 4, so the locker is toggled an even number of times and ends closed. Only a square has an unpaired divisor: for 16, the divisor 4 pairs with itself. Small cases gave the pattern, and the explanation turned it into a proof.

• Say out loud: "Let me try two, three, four first." Interviewers are waiting for exactly this step.
• A pattern you found is not yet an answer. Explain why it holds, and only then carry it to 100.

Deeper: two puzzles where small cases are the only way in.

This builds on what you haven't done yet: chapter 3, “Small cases”

"This is a game of many moves. Where do I start?"

When a puzzle is a sequence of steps, starting from the first is often hopeless: there are too many options. The last step, though, is usually simple. Solve it, then the one before, and so on back to the start. It's the same "small cases" idea, except that what's small here is the end of the game.

• If the puzzle is a game or a multi-step process, ask yourself: "What does the last step look like?"
• A table of positions built from the end is a ready answer for the interviewer: easy to show and to check.

Deeper: pirates who split gold from the end, and a lake best read from its last day.

"How would I know how many there are? I don't remember numbers like that."

Estimation questions, also called Fermi questions, don't test your memory. They are asked to see how you break an unknown number into a few known ones, state your assumptions and check that the result is plausible. Being within a factor of two is usually more than enough.

With the real numbers the estimate gives about 300 thousand a day, about a sixth short of the truth. That gap is interesting too, and worth saying aloud: the population is not steady but growing, so there are more young people than in a steady world, and they have more babies. Saying which way your estimate may be off and why is the best way to finish an answer.

• First the formula in words ("population divided by life expectancy"), then the numbers. The formula is what the interviewer is rating.
• Round boldly: 8 billion and 80 years are easy to do in your head, and accuracy hardly suffers.
• Check the result another way or against a number you know, and say which way it might be off.

Deeper: a puzzle where the sense of scale fails almost everyone.

This builds on what you haven't done yet: chapter 1, “What is really rated”

"Five minutes in and I still don't see a solution. What do I say?"

A dead end in an interview is a normal part of the puzzle, not a failure. Interviewers often deliberately pick a puzzle few people finish in ten minutes, to see what you do when you don't know.

• Break any silence longer than half a minute, even with no idea yet: say what you're checking right now.
• "I don't know" is not the end of an answer but its start: "I don't know, but I can say it's certainly no more than…".

"Hundreds of thousands of candidates and only a handful of tests. Is that even possible?"

Many puzzles ask: how many tests do you need to find one item among many, for sure? Instead of trying strategies, count how many different outcomes your tests can produce together. If there are fewer outcomes than possibilities, no strategy will help. If there are as many or more, it can usually be done.

What if a test has three outcomes instead of two? A balance shows "left heavier", "right heavier" or "equal", so n weighings give 3ⁿ different outcomes. It gets more interesting when several tests run at once: then you count not questions but combinations of all the tests' answers together. Both puzzles below come down to exactly this count.

• First count the bound: how many distinct outcomes all the tests give together, and how many possibilities you must tell apart. That is a lower bound for any strategy.
• A good test splits the possibilities into equal parts. A question that is almost always answered "no" tells you almost nothing.

Deeper: two classic puzzles about counting outcomes.

This builds on what you haven't done yet: chapter 7, “What one test tells you”

"Binary search is the best, surely. Why doesn't it work here?"

"For sure" in an interview means "in the worst case". It helps to imagine an evil opponent who knows your strategy and always answers so as to hurt you most. A strategy is good if even they can't force you into more steps.

• When the question says "for sure" or "guaranteed", count the worst case and imagine an opponent who will arrange it.
• A limited resource (eggs, races, mistakes) changes the best strategy. Run the familiar algorithm through the worst case before proposing it.

Deeper: the same idea with 100 floors, and in a horse tournament without a stopwatch.

"I keep trying and there's always a gap left. Am I doing something wrong?"

An invariant is a quantity that doesn't change whatever you do. If it would have to be different at the end than at the start, the goal is unreachable, and you don't need to try every option to prove it. In an interview it is the shortest path from "I can't make it work" to "it's impossible, and here's why".

• If the question asks "is it possible" and you keep failing, look for what doesn't change: colour, parity, a sum, a remainder.
• Parity is the most common interview invariant: it works for dominoes, hats and toggles alike.

Deeper: a hundred people, hats and one parity for everyone.

This builds on what you haven't done yet: chapter 6, “Shaping an answer”

"I'll just do the best thing at each step. What could go wrong?"

A greedy strategy, always doing what looks best right now, is a natural first step and a good "first rough answer" from chapter 6. But in scheduling puzzles it often loses, and a lower bound helps you check: the least time it could possibly take, however you arrange things.

• Give the greedy answer first, then compute a lower bound. If they differ, the better schedule lies in that gap.
• The most expensive resource (here a toaster slot standing empty) shows where greed wastes time.

Deeper: a bridge at night, a torch, and a puzzle where greed loses.

This builds on what you haven't done yet: chapter 2, “Read the question again”

"Two options are left, so it's fifty-fifty?"

"Two options, so it's half and half" is the most common mistake in probability puzzles. Options aren't always equally likely: what matters is not how many are left but how many ways you could have arrived at what you see.

• List equally likely elementary outcomes (here six sides), not "the options left".
• Ask how exactly you learned what you know: who chose, what was shown and why. The answer depends on it, as in the Monty Hall problem from chapter 2.

Deeper: two puzzles where "half and half" is a trap.

"There are so many cases. Do I really have to go through them all?"

In average puzzles you often don't need the full distribution. It's enough to split the quantity into a sum of simple parts: the average of a sum is the sum of the averages, even when the parts depend on each other. And symmetry gives each part's average with no calculation at all.

Look at the last number: in about 37% of evenings nobody gets their own hat, so at least one person does in 63%. That's the second trick of this chapter: when asked "at least one", compute the opposite, "none", and subtract it from one. That is how the birthday problem is solved too.

• The average of "how many" is the sum of each one's chance. Dependence between them doesn't get in the way.
• Compute "at least one" through "none". It's almost always easier.

Deeper: a sticker album whose average is a sum of simple parts, and a room where "at least one pair" is computed through "none".

This builds on what you haven't done yet: chapter 3, “Small cases”

"Take the first offer or wait for a better one?"

Stopping puzzles are like life: options arrive one at a time, a rejection can't be undone, and nothing is known about those still to come. The big case isn't visible at once, so we start small (chapter 3): three candidates have only six possible orders, few enough to list by hand.

• Listing all cases for a small size is a full-fledged interview answer, if you then say what you see in the table and how it carries over to larger numbers.
• The first options are useful even when you reject them: they set the bar for the rest.

Deeper: the same with a hundred candidates.

This builds on what you haven't done yet: chapter 2, “Read the question again”chapter 3, “Small cases”chapter 9, “Invariants and parity”

"I was given a hint. Does that count against me?"

A hint is an ordinary part of the conversation: the interviewer gives it to keep the puzzle moving and to see more. What's rated is not that you needed it but what you did with it: whether you saw where it points and connected it to what you had already tried.

Notice what each hint did: the first was a small case (chapter 3), the second removed an unnoticed constraint (chapter 2), the third was an invariant: the difference in heads between the piles stays under your control (chapter 9). Interview hints almost always point to one of this course's tools. So when you hear one, say which technique it points to and how it changes your plan.

• When you hear a hint, restate it and say what you'll try: "Right, so for two coins…"
• Don't throw away what you've done: explain how the hint fits with your attempts.
• If a hint is unclear, ask directly: "Are you pointing me to a small case?" That's a signal too, not a weakness.

This builds on what you haven't done yet: chapter 2, “Read the question again”chapter 5, “A rough estimate”chapter 6, “Shaping an answer”chapter 7, “What one test tells you”chapter 12, “Symmetry and the average”

"You have five minutes per puzzle. Think out loud."

How to practise: start the timer and solve out loud, to a voice recorder or a friend. If you're stuck, take the next hint, as you would from an interviewer. Then pick an answer and honestly tick what you did along the way. Each puzzle trains a chapter of the course.

Practising on catalogue puzzles is easy in the "Interview trainer": a random puzzle, a timer, three hints and a self-review of your reasoning.

• Xinfeng Zhou · A Practical Guide to Quantitative Finance InterviewsThe quants' "green book": brainteasers in chapter 2, probability in chapter 4.
• Gayle Laakmann McDowell · Cracking the Coding InterviewOn software interviews; maths and logic puzzles in chapter 6.
• William Poundstone · Are You Smart Enough to Work at Google?Puzzles from tech company interviews and how to approach them.
• William Poundstone · How Would You Move Mount Fuji?The history of puzzle interviews at Microsoft and across Silicon Valley.
• Anany Levitin, Maria Levitin · Algorithmic PuzzlesChapter 1 is a short tutorial on solving strategies, then puzzles by difficulty.
• Frederick Mosteller · Fifty Challenging Problems in ProbabilityClassic probability problems with solutions, short and honest.
• Peter Winkler · Mathematical Puzzles: A Connoisseur's CollectionA collection of puzzles with elegant solutions, for those who want more.

All books with the chapters where catalogue puzzles appear are on the site's shelf.