13 Quant Probability and Brainteasers Interview Questions and Answers

Short answer: Six. Solve with two states: E₀ (no progress) and E_H (last flip was heads); the system gives E_H = 4, E₀ = 6. For contrast: the pattern HT takes only 4 flips on average.

In depth:

1. States — S₀: last flip was not heads (or start); S_H: last flip was heads. From S_H a head finishes the game, a tail throws you back to S₀ — all progress burns.
2. Equations — from each state you pay 1 flip and transition with probability ½ each way.
3. Why HH takes longer than HT — for HT a "failure" is not fatal: you wait for a tail after a head, and if a second head shows up, it itself stays the first symbol of HT — progress is preserved. For HH a tail resets everything. Hence E[HT] = 4 < E[HH] = 6, even though both patterns have the same two-flip probability.

 S₀ ──½ H──► S_H ──½ H──► HH ✓
 ▲│½ T          │½ T
 └┘◄────────────┘
 E₀ = 1 + ½·E_H + ½·E₀
 E_H = 1 + ½·0  + ½·E₀   ⇒  E_H = 4,  E₀ = 6

⚠️ Common mistake: answering "4" — P(HH) = ¼ per two flips, so wait 4. For self-overlapping patterns the mean waiting time is not 1/P — a failure sends you back to zero, which stretches the wait.

Short answer: The von Neumann trick: flip the coin in pairs. HT → outcome A, TH → outcome B, HH or TT → discard the pair and flip again. P(HT) = P(TH) = pq, so the result is exactly 50/50 for any p.

In depth:

1. Why it is fair — within a pair the orders HT and TH are symmetric: p·q versus q·p. Conditional on the pair being "decisive", each outcome has probability exactly ½ — exact, not approximate.
2. The cost — a pair is decisive with probability 2pq, so the expected number of pairs is 1/(2pq) and of flips 2·1/(2pq) = 1/(pq).
3. Numbers — p = ½: 4 flips; p = 1/3: pq = 2/9, so 4.5 flips on average; the stronger the bias, the more fairness costs.

def fair_flip(biased):          # biased() -> 'H' | 'T'
    while True:
        a, b = biased(), biased()
        if a != b:              # HT or TH — equal probabilities: p*q
            return 'A' if a == 'H' else 'B'
        # HH / TT — discard the pair and repeat
# E[flips] = 1/(p*q); for p = 1/3 that is 1/(2/9) = 4.5

⚠️ Common mistake: ad-hoc schemes — a single flip with a decision rule, or parity of heads in a fixed-length run. Those give a probability that depends on p, not exactly ½. Von Neumann works because it compares symmetric orderings.

Short answer: Switch: switching wins the car with probability 2/3, staying wins 1/3. The key assumption is that the host is informed: he always opens a door with a goat. If he opened a random door (and happened to reveal a goat), the odds would be 1/2 each.

In depth:

1. Your first pick finds the car with probability 1/3 — and the host opening a door does not change that: he can always show a goat, so the reveal carries no news about your door.
2. The remaining 2/3 concentrates on the single unopened door — the host used his knowledge to "filter out" a goat for you.
3. You picked door 1 — all cases:

Switching wins in 2 cases out of 3.

⚠️ Common mistake: "two doors left, so it is 50/50." That is true only for an uninformed host (the "Monty Fall" variant): conditioning on an accidentally revealed goat really does give 1/2. The host being informed is the whole point of the problem.

Short answer: By Bayes: 1024/(1024 + 99) = 1024/1123 ≈ 91.2%. The prior rarity (1/100) is almost fully outweighed by the fact that a fair coin produces 10 heads in a row only with probability 1/1024.

In depth:

1. Hypotheses — D: the coin is double-headed, P(D) = 1/100; F: fair, P(F) = 99/100.
2. Likelihoods — P(10H | D) = 1; P(10H | F) = (1/2)¹⁰ = 1/1024.
3. Bayes — the numerator is the "path" through the double-headed coin, the denominator is every path to 10 heads:

P(D | 10H) = P(10H|D)·P(D) / [ P(10H|D)·P(D) + P(10H|F)·P(F) ]
           = 1·(1/100) / [ 1·(1/100) + (1/1024)·(99/100) ]
           = 1024 / (1024 + 99)
           = 1024/1123 ≈ 0.912

A handy odds intuition: prior odds D:F = 1:99, likelihood ratio 1024:1, posterior odds 1024:99.

⚠️ Common mistake: forgetting the 99 fair coins, each of which can also produce 10 heads with probability (1/2)¹⁰ — and answering "almost surely double-headed, ≈ 1." The denominator must include both paths; that factor of 99 is exactly what keeps the answer at 91% rather than 99.9%.

Short answer: 1/3, and with the Tuesday detail — 13/27. The condition "at least one boy" leaves three equally likely pairs (BB, BG, GB), of which one is both boys. A seemingly irrelevant detail ("born on Tuesday") changes the event we condition on — and the answer shifts toward 1/2.

In depth:

1. Base case — the space of pairs by birth order: BB, BG, GB, GG. The condition strikes out GG → P(BB) = 1/3.
2. Contrast — "the older one is a boy" leaves BB, BG → 1/2. The exact phrasing of the condition decides everything.
3. Tuesday boy — count (sex, weekday) combinations per child: 14×14 = 196 equally likely pairs. "At least one Tuesday boy": 14 + 14 − 1 = 27 pairs. Of those, both boys: 7 + 7 − 1 = 13. Result 13/27 ≈ 0.481.

⚠️ Common mistake: waving it off — "the weekday changes nothing." It does: the more specific the description, the less double-counting of two-boy families, and the closer the answer gets to 1/2 (as when a specific child is identified).

Short answer: e ≈ 2.718. The tail probability P(N > n) equals the probability that the sum of n uniforms has not yet exceeded 1 — the volume of a simplex, 1/n!. Summing the tails gives E[N] = Σ 1/n! = e.

In depth:

1. The event {N > n} — the first n draws have not broken through 1 yet: U₁ + … + U_n ≤ 1.
2. Geometry — {x ∈ [0,1]ⁿ : x_i ≥ 0, Σx_i ≤ 1} is the standard simplex; its volume is 1/n! (proved by induction on n, or by ordering n points).
3. Tail-sum formula — for integer-valued N: E[N] = Σₙ₌₀^∞ P(N > n). This is the key device — it sidesteps computing the full distribution of N.

P(N > n) = P(U₁ + … + U_n ≤ 1) = Vol(simplex) = 1/n!

E[N] = Σ_{n=0}^{∞} P(N > n)
     = 1/0! + 1/1! + 1/2! + 1/3! + …
     = 1 + 1 + 0.5 + 0.1667 + …  = e ≈ 2.71828

Bonus for the interviewer: by the same method, the expected number of draws to exceed a threshold t ∈ [0,1] is eᵗ.

⚠️ Common mistake: reasoning "the average draw is 1/2, so you need 2." N and the draws are dependent (you stop precisely on a large draw), so Wald's identity does not apply directly — the honest tail-sum route gives e, not 2.

Short answer: 1/4. The pieces form a triangle if and only if no piece is longer than half the stick; on the unit square of break points (x, y) that is a region of area 1/4.

In depth:

1. Criterion — the triangle inequality for pieces a + b + c = 1 is equivalent to a single condition: max(a, b, c) < 1/2 (the longest piece is shorter than the other two combined).
2. Make it geometric — let x < y be the break points on [0,1]; pieces: x, y − x, 1 − y. Conditions: x < 1/2, y > 1/2, y − x < 1/2.
3. Area — for x < y this is the triangle with vertices (0, ½), (½, ½), (½, 1), area 1/8; the symmetric case x > y adds another 1/8. Total 1/4.

Pieces (for x < y):  x | y − x | 1 − y
Triangle ⇔ every piece < 1/2:
   x < 1/2,   y > 1/2,   y − x < 1/2

  y                        
  1 ┌─────┬─────┐   ▲ — favorable zone x<y (1/8)
    │     │ ▲   │   ▼ — mirrored zone  x>y (1/8)
  ½ ├─────┼─────┤
    │   ▼ │     │   area = 1/8 + 1/8 = 1/4
  0 └─────┴─────┘
    0     ½     1  x

⚠️ Common mistake: mixing up the model. "Break at two random points at once" gives 1/4; "break at a random point, then break the longer piece" is a different problem with a different answer. In an interview, pin down the breaking protocol first.

Short answer: With one reroll — 4.25: keep 4–6 (anything above E[reroll] = 3.5), otherwise reroll. With two rerolls — 14/3 ≈ 4.67: on the first roll keep only 5–6, because the comparison point is now 4.25.

In depth:

1. Work backwards (backward induction) — the last roll cannot be replaced by anything: its value is 3.5.
2. One reroll — keep x if x > 3.5, i.e. 4, 5, 6 (average 5). Value: ½·5 + ½·3.5 = 4.25.
3. Two rerolls — giving up the first roll is now worth 4.25, so the threshold rises: keep only 5 and 6 (average 5.5). Value: (2/6)·5.5 + (4/6)·4.25 = 11/6 + 17/6 = 28/6 = 14/3 ≈ 4.67.

⚠️ Common mistake: in the two-reroll game, comparing the first roll to 3.5 and keeping a 4. By declining a roll you get not "one roll" but a game worth 4.25 — each stage's threshold comes from the value of the remaining tail, not from 3.5.

Short answer: 10. Group the cube's vertices by distance to the target (d = 3, 2, 1, 0) — by symmetry this is a Markov chain with three non-absorbing states; the linear system for hitting times gives E₃ = 10.

In depth:

1. Collapse by symmetry — vertex coordinates ∈ {0,1}³; distance to target = number of mismatched bits. All vertices in a class are equivalent, so three unknowns E₁, E₂, E₃ suffice.
2. Transitions — each step flips exactly one bit: from d = 3 all 3 edges lead to d = 2; from d = 2 two edges lead to d = 1 and one back to d = 3; from d = 1 one edge hits the target, two lead to d = 2.
3. System and solution — from E₂ = 2 + E₁ and E₁ = 1 + (2/3)E₂ we get E₁ = 7, then E₂ = 9, E₃ = 1 + E₂ = 10.

 start (d=3) ──► d=2 ──► d=1 ──► target (d=0)
                 ▲ │      ▲ │
                 └─┘◄─────┘ └─ 1/3 to target

 E₃ = 1 + E₂
 E₂ = 1 + (2/3)E₁ + (1/3)E₃
 E₁ = 1 + (2/3)E₂ + (1/3)·0
 ⇒  E₁ = 7,  E₂ = 9,  E₃ = 10

⚠️ Common mistake: setting up 8 unknowns — one per vertex — and drowning in arithmetic. Collapsing by symmetry classes is exactly the move the interviewer wants to see; it scales to hypercubes and larger graphs too.

Short answer: 10·(1 − (9/10)¹⁰) ≈ 6.51. The technique is linearity of expectation over indicator variables: for each floor, compute the probability at least one person exits there, and add them up — dependence between floors does not matter.

In depth:

1. Indicators — I_k = 1 if at least one passenger exits on floor k. Number of stops S = I₁ + … + I₁₀.
2. One floor — nobody picks floor k with probability (9/10)¹⁰ ≈ 0.349, so E[I_k] = P(I_k = 1) = 1 − (9/10)¹⁰ ≈ 0.651.
3. Linearity — E[S] = Σ E[I_k] = 10·(1 − (9/10)¹⁰) ≈ 6.513. The key point: linearity of expectation does not require the indicators to be independent — say this to the interviewer explicitly, that is the skill being tested.

E = 10 * (1 - (9/10)**10)      # 6.5132...

# sanity-check by simulation
import random
sim = sum(len({random.randrange(10) for _ in range(10)})
          for _ in range(100_000)) / 100_000   # ≈ 6.51

⚠️ Common mistake: trying to compute the full distribution of occupied floors head-on (Stirling numbers, inclusion-exclusion) — it works, but takes an order of magnitude longer. The indicator decomposition solves it in three lines, and this is the standard test of whether you know the trick.

Short answer: 7. Five group races, then a race of the winners — it crowns the champion and lets you prune almost everyone. Exactly 5 candidates remain for places 2–3 — a seventh race settles them.

In depth:

1. Races 1–5 — split into groups A–E and learn the order within each.
2. Race 6 (the winners) — say they finish A1 > B1 > C1 > D1 > E1. A1 is the fastest horse, question closed.
3. Pruning — a horse is out of the top 3 if at least 3 horses are already guaranteed faster: groups D and E drop out entirely (even D1 is at best 4th), from group C only C1 survives (at best 3rd), from B — B1 and B2, from A — A2 and A3.
4. Race 7 — {A2, A3, B1, B2, C1}: the first two take places 2 and 3.

Races 1–5:  A: A1>A2>A3>…   B: B1>…   C: C1>…   D: …   E: …
Race 6:     A1 > B1 > C1 > D1 > E1   ⇒  #1 = A1
Out:        D*, E*  (A1,B1,C1 already ahead of D1)
            C2+     (C1 itself is at best 3rd)
            B3+     (ahead of B3: A1, B1, B2)
            A4, A5  (ahead of them: A1, A2, A3)
Race 7:     A2, A3, B1, B2, C1  →  places 2 and 3

⚠️ Common mistake: stopping at 6 races and taking the winners'-race top 3. B2 may be faster than C1, and A2 faster than B1: group races only compare horses within groups, so the seventh race is mandatory.

Short answer: 23. Compute via the complement: the probability that all birthdays are distinct is the product Π(1 − k/365); at n = 23 it drops to ≈ 0.493, so the probability of a match is ≈ 0.507 > 1/2.

In depth:

1. Complement — the direct event "at least one match" is messy; "all distinct" is a single product: the k-th person misses everyone before them with probability (365 − k)/365.
2. Intuition — pairs — matches happen between pairs of people, and there are C(23, 2) = 253 pairs: the number of "chances" grows quadratically in n, which is why the threshold is so low.
3. Quick estimate — P(no match) ≈ exp(−n²/730); setting it to ½ gives n ≈ √(730·ln 2) ≈ 22.5.

p_unique = 1.0
for k in range(23):
    p_unique *= (365 - k) / 365
print(1 - p_unique)    # 0.5073 — already above 1/2
# at n=22: 0.4757; at n=50: 0.9704; at n=70: 0.9992

⚠️ Common mistake: the intuition "you need ~183 people, half of 365" — that answers a different question: how many people until someone matches you specifically (threshold 253 there). A match between "someone and someone" arrives quadratically sooner.

Short answer: Take any 5 coins and flip all of them. If the picked five contains k heads, after flipping it contains 5 − k heads — exactly as many as remain in the other group. No information about individual coins is needed.

In depth:

1. Split — group X: any 5 coins, group Y: the other 5. Say X received k heads — then Y has 5 − k (there are five heads in total).
2. Flip — X currently has k heads and 5 − k tails; flip all 5 coins: heads become tails and vice versa, so X now has 5 − k heads.
3. Invariant — the equality 5 − k = 5 − k holds for every k from 0 to 5: the solution is deterministic, not probabilistic.
4. Generalization — n heads among any number of coins: take any n coins and flip them all.

Group X (picked 5):   k heads, 5−k tails
Group Y (the rest):   5−k heads

Flip everything in X:  k heads → k tails,
                       5−k tails → 5−k heads
Result:  X: 5−k heads  =  Y: 5−k heads ✓   (for any k)

⚠️ Common mistake: looking for a way to "detect" heads — by touch, by weight, by rearranging. The problem is solved not by information but by an invariant: flipping a fixed-size group equalizes the count automatically. Trying to count the coins signals to the interviewer that you do not know the trick.