Skip to content
Tutorials Center
My learning

Topics

Lesson 52 of 77 · CS Fundamentals Interview Questions

Interview Puzzles and Brain Teasers

Solve classic interview puzzles: two eggs, bridge crossing, water jugs, weighing, Monty Hall, the birthday paradox and Fermi estimates, verified in code.

Many companies still ask a puzzle or an estimation question, not because the answer matters, but because how you think does. The interviewer is watching whether you restate the problem, try small cases, state your assumptions, notice patterns, and check your result. A candidate who says "I will try three floors first" and works toward the answer beats one who recites a memorized solution and cannot explain it.

This lesson gives a repeatable approach and then walks through the most common puzzle families. Every claimed answer was verified by a program: brute-force search for the logistics puzzles, simulation for the probability puzzles, and an estimate with a visible range for the Fermi question. The programs run in the Python runner. Interview-day habits like thinking aloud are in Thinking Out Loud, and the search and dynamic programming ideas used here are covered in Recursion and DP Questions and Trees and Graphs Questions.

A puzzle-solving routine

Restate Say the problem in your own words.
Shrink Try 1, 2, 3 before 100.
Find structure Symmetry, invariants, pairs.
Check Test your answer on a small case.

Silence is the enemy; narrate your thinking.

1 / 2

How should you approach a puzzle?

  1. Clarify the rules. Can you do X? Is the fuse uniform? Is the answer the worst case or the average case? Many puzzles are lost on an unstated assumption.
  2. Shrink the problem. Solve it for 1, 2 and 3 items and look for the pattern. This is also the first step toward a recursive or dynamic-programming solution.
  3. Look for structure: symmetry, parity, invariants, divide in half, group in threes, or "what is the worst case, and can I make all cases equal?"
  4. Write a candidate answer and test it on an edge case.
  5. If you recognise the puzzle, say so. Honesty is respected; then explain the solution fully rather than just stating it.

Two eggs and 100 floors

The puzzle: a building has 100 floors. An egg breaks if dropped from floor F or higher and survives below it. You have two eggs. What is the minimum number of drops that guarantees you find F in the worst case?

The reasoning: with one egg you must go floor by floor. With two, drop the first egg at floor 14. If it breaks, you test floors 1 to 13 with the second egg (at most 13 more drops, 14 in all). If it survives, go up 13 floors (to 27): if it breaks there, the second egg has 12 floors to test, so the total is still 14. Each step goes up one floor fewer, so the worst case stays equal. The jumps 14 + 13 + 12 + ... + 1 = 105 cover 100 floors. In general you need the smallest n with n(n + 1)/2 ≥ 100, so n = 14.

The bridge and the torch

The puzzle: four people must cross a bridge at night. They have one torch, the bridge holds at most two people at a time, and a pair walks at the speed of the slower person. Their times are 1, 2, 5 and 10 minutes. What is the minimum total time?

The reasoning: the obvious plan (the fastest person escorts everyone) costs 19 minutes. The better plan sends the two slowest together so their expensive times are paid once: (1, 2) cross [2 min], 1 returns [1], (5, 10) cross [10], 2 returns [2], (1, 2) cross [2] = 17 minutes. A search over every possible sequence of crossings confirms nothing is faster.

100 doors

The puzzle: 100 closed doors. On pass k (for k from 1 to 100) you toggle every k-th door. Which doors are open at the end?

The reasoning: door n is toggled once for each of its divisors. Divisors normally come in pairs (d and n/d), giving an even number of toggles, so the door ends closed. Only perfect squares have an odd number of divisors (the square root pairs with itself), so doors 1, 4, 9, ..., 100 stay open: ten doors.

Python Eggs, the bridge and the doors, checked by search

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Water jugs and weighing puzzles

Water jugs: with a 3-litre and a 5-litre jug and unlimited water, measure exactly 4 litres. These are state-space search problems: a state is (water in jug A, water in jug B), moves are fill, empty or pour, and breadth-first search finds the shortest path. A solution exists whenever the target is a multiple of the gcd of the jug sizes and fits in the larger jug (so 4 and 6 cannot measure 5, since both sizes are even).

Nine balls, one heavier: find the heavy ball in two weighings on a balance scale. Split into three groups of three. Weigh group 1 against group 2: the heavier side holds the heavy ball, and if they balance it is in group 3. Then weigh two balls of that group against each other, with the same logic. The idea is that each weighing has three outcomes (left heavy, right heavy, balance), so two weighings distinguish 3 × 3 = 9 possibilities. This generalizes: n weighings handle 3ⁿ balls.

Python Water jugs by BFS, and the weighing strategy on every case

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Burning ropes: two ropes each burn out in exactly 60 minutes, but unevenly. Measure 45 minutes. Light rope A at both ends and rope B at one end. A burns out after 30 minutes. At that moment light B's other end: the remaining half of B (which would take 30 more minutes) now burns from both ends and takes 15. Total: 45 minutes. The trick, lighting both ends, halves a rope's remaining time no matter how unevenly it burns.

Probability puzzles: Monty Hall and the birthday paradox

Monty Hall: behind one of three doors is a car. You pick a door; the host, who knows where the car is, opens a different door that hides a goat and offers you a switch. Should you? Yes: switching wins 2/3 of the time. Your first pick is right with probability 1/3, and that does not change when the host opens a goat door; so the other unopened door carries the remaining 2/3. (The host's knowledge matters: if he opened a door at random, the answer would be different.) If a listener resists, imagine 100 doors: you pick one, the host opens 98 goat doors, and the remaining door is obviously the better bet.

Birthday paradox: how many people must be in a room for it to be more likely than not that two share a birthday? The answer is 23, surprisingly small, because you compare pairs and 23 people make 253 pairs. The exact probability that all birthdays differ is (365/365) × (364/365) × ... × (343/365), and one minus that is the answer.

Python Monty Hall, the birthday paradox and a Fermi estimate

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Estimation (Fermi) questions

"How many piano tuners are there in a city of one million?" has no exact answer; it tests structured thinking. The recipe: break the question into factors you can estimate, state each assumption aloud, multiply, and give a range. Households (people ÷ 4) × share with a piano × tunings per year gives the yearly work; one tuner's capacity is tunings per day × working days. In the program above the middle estimate is about 14 tuners, with a plausible range from about 4 to 21. The interviewer cares that the range is the right order of magnitude (tens, not thousands) and that you can say which assumption matters most. Two habits help: use round numbers, and sanity-check the answer ("14 tuners for a million people: plausible").

More puzzles: Cheryl's birthday, hat puzzles, tic-tac-toe, matchsticks and the Rubik's cube

These five puzzle types fill out the catalog. As above, each answer is verified by a program, so you can trust it and change the inputs.

Cheryl's birthday (knowledge puzzles)

Puzzle. Cheryl gives Albert and Bernard ten possible dates: May 15, 16, 19; June 17, 18; July 14, 16; August 14, 15, 17. She tells Albert only the month and Bernard only the day. Then:

  1. Albert: "I don't know the birthday, but I know that Bernard doesn't know either."
  2. Bernard: "At first I didn't know, but now I do."
  3. Albert: "Now I know too."

When is Cheryl's birthday?

Method. Turn each sentence into a filter on the list of dates, in the order spoken. Statement 1: Albert is sure Bernard does not know, so none of the days in Albert's month can be a day that appears only once. The days 18 and 19 each appear once (June 18, May 19), so Bernard would know if he had them. That removes May and June. Statement 2: Bernard now knows, so his day must appear exactly once among the remaining dates (July 14, July 16, August 14, August 15, August 17). The day 14 appears twice, so it goes, leaving July 16, August 15 and August 17. Statement 3: Albert now knows, so his month must have exactly one date left. August has two (15 and 17), July has one, so the birthday is July 16.

Python Solve Cheryl's birthday by filtering

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Hat puzzles (information and parity)

Puzzle. n prisoners stand in a line, all facing forward, so each sees the hats of everyone in front of them (not their own or those behind). Each hat is black or white, assigned at random. Starting from the back, each prisoner calls out a color; they are freed if it matches their own hat. They may agree on a strategy beforehand but cannot signal otherwise. How many can you guarantee to save?

Answer. n - 1. The last prisoner (who sees everyone) says "black" if he sees an even number of black hats and "white" if odd. That sacrifices him (50% chance), but the others can now decode: the next prisoner counts the black hats in front of him and compares the parity with what he heard. If it differs, his own hat is black; otherwise white. Everyone after him tracks the earlier correct answers and updates the parity, so every prisoner except the first is right. The idea is that one bit of information can carry a parity of everything seen.

Python Verify the parity strategy on every possible hat assignment

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same trick, using parity or a sum modulo k to compress information, solves the "10 people with hats numbered 0 to 9 who each guess their own number" variant: each person guesses the number that makes the total sum modulo 10 equal to their own index.

Tic-tac-toe (game trees and minimax)

Questions. "Can the first player always win?" No, with perfect play it is a draw. "How would you write an unbeatable player?" Search the game tree with minimax: a position's value is the best outcome for the player to move, assuming the opponent also plays best (+1 win, 0 draw, -1 loss). There are only 5,478 reachable positions, so a full search is instant; for bigger games you add alpha-beta pruning and a heuristic evaluation with a depth limit. Mention symmetry (rotations and reflections reduce the 9 opening moves to 3 distinct ones) and memoization of positions.

Python Minimax: value of the game, and every first move

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every first move is worth 0 for perfect play, which is why a draw is the answer. In the last position every move except blocking at index 2 scores -1 (a loss), so minimax finds the block without being told about "threats".

Matchstick puzzles (and the matchstick game)

There are two kinds. Geometric puzzles ("move one match to fix the equation", "make four triangles from six matches") are solved by trying small modifications systematically, and by remembering that a 3D arrangement is allowed when the statement does not forbid it (six matches make four equilateral triangles as a tetrahedron).

The matchstick game is a Nim variant that is a favorite: there are 21 matches; players alternately take 1, 2 or 3; the player who takes the last match wins. Do you want to go first? Work backward from the end. Positions where you must lose are those where the remaining count is a multiple of 4 (whatever you take, the opponent takes 4 - k and restores a multiple of 4). So with 21 (not a multiple of 4), go first, take 1, and then always answer with 4 - (opponent's take). If the last-taker loses instead, the losing positions shift to 4k + 1.

Python Find the winning positions by working backward

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Rubik's cube

Cube questions are rarely about solving it in the interview; they are about counting and reasoning with permutations. Facts to know:

  • The 3x3x3 cube has 43,252,003,274,489,856,000 reachable positions (about 4.3 x 10^19). The count comes from corner and edge permutations and orientations, divided by the constraints that make only some combinations legal: the corner twists must sum to a multiple of 3, the edge flips to a multiple of 2, and the permutation parity of corners and edges must match.
  • God's number is 20: every position can be solved in at most 20 moves (in the half-turn metric), proved in 2010 with massive computation.
  • Moves are permutations, so repeating a move sequence eventually returns to the start; the number of repeats is the order of that permutation (for example, the common sequence R U has order 105).
  • Beginner methods are layer by layer; speedcubers use CFOP, and machine solvers use Kociemba's two-phase algorithm. A "how would you write a solver" answer is: model the cube as permutations, and use IDA* or two-phase search with pruning tables.
Python Count the positions and find the order of a permutation

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The order of a permutation is the least common multiple of its cycle lengths. The known result that R U repeats every 105 times is consistent with cycles whose lengths multiply out through lcm(3, 5, 7) = 105; computing it for real needs a full cube model.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. With two eggs and a 100-floor building, what is the minimum number of drops that guarantees finding the breaking floor?

    Drop at floors 14, 27, 39, ... going up one fewer each time, so the worst case is always 14 drops. 14 is the smallest n with n(n+1)/2 at least 100.
  2. 2. People take 1, 2, 5 and 10 minutes to cross a bridge two at a time with one torch. What is the minimum total time?

    Send (1,2), return 1, send (5,10), return 2, send (1,2): 2 + 1 + 10 + 2 + 2 = 17.
  3. 3. After 100 passes toggling every k-th door, which doors are open?

    A door is toggled once per divisor. Only perfect squares have an odd number of divisors, so only they end open.
  4. 4. In Monty Hall, the host knowingly opens a goat door. What is the probability of winning if you switch?

    Your first choice is right with probability 1/3. The other unopened door holds the remaining 2/3.
  5. 5. How many people are needed for a better than 50% chance that two share a birthday?

    23 people create 253 pairs, and the probability that all birthdays differ drops to about 49.3%.

Summary

  • Restate, shrink the problem, look for structure, test your answer, and narrate throughout.
  • Two eggs and 100 floors needs 14 drops (the jumps shrink by one each time); the bridge puzzle takes 17 minutes by sending the two slowest together.
  • Doors toggled once per divisor end open only for perfect squares; water jugs are a breadth-first search; n weighings distinguish 3ⁿ balls.
  • Monty Hall: switching wins 2/3; the birthday paradox crosses 50% at 23 people because of the number of pairs.
  • For Fermi estimates, multiply factors you can defend, give a range and sanity-check the order of magnitude.
  • Knowledge puzzles are solved by filtering the possibilities after each statement; Cheryl's birthday is July 16.
  • Parity carries information (the hat line saves n-1 prisoners), minimax solves small games such as tic-tac-toe (a draw), and Nim-style games are solved by working backward.
  • Rubik's cube questions are about counting (about 4.3e19 positions) and the order of a permutation, which is the lcm of its cycle lengths.

Next: Git and Linux Questions, where the topic moves from puzzles to everyday tools.