The question bank

Order doesn’t matter, so it’s a combination: $\left(\genfrac{}{}{0ex}{}{10}{3}\right)=\frac{10\cdot 9\cdot 8}{3!}=120$. A quick warm-up; answer instantly and move on.

(a) $\frac{1}{6}(1+2+\cdots +6)=3.5$.

(b) A re-roll is worth 3.5, so keep 4, 5 or 6 and re-roll 1, 2 or 3: $\frac{3}{6}\cdot 3.5+\frac{1}{6}(4+5+6)=4.25$.

After paying $1, a re-roll is worth $3.5-1=2.5$, so only re-roll a 1 or a 2: $\frac{2}{6}\cdot 2.5+\frac{1}{6}(3+4+5+6)=\frac{23}{6}$.

Let $V$ be the value. Keeping faces $t$ and above gives $V=\frac{1}{6}{\sum }_{x\ge t}x+\frac{t-1}{6}(V-1)$.

• $t=4$: $V=2.5+\frac{1}{2}(V-1)\Rightarrow V=4$.
• $t=3$: $V=3+\frac{1}{3}(V-1)\Rightarrow V=4$.
• $t=5$: $V=\frac{11}{6}+\frac{4}{6}(V-1)\Rightarrow V=3.5$.

The rule “keep anything above $V-1=3$” is self-consistent: 3 itself is break-even.

Product of two independent dice: $E[XY]=E[X]E[Y]=3.5^2=12.25$. Square of one die: $E[X^2]=\frac{91}{6}\approx 15.17$.

For the median $M$ use $E[M^2]=(E[M]{)}^2+\mathrm{Var}(M)$. By symmetry $E[M]=3.5$, so $E[M^2]=12.25+\mathrm{Var}(M)$, while one die gives $12.25+\frac{35}{12}$. The median of five dice is far less spread out than one die (an extreme median needs three 6s or three 1s), so $0<\mathrm{Var}(M)<\frac{35}{12}$ and it lands strictly between the other two. Exact enumeration over $6^5$ outcomes gives $E[M^2]\approx 13.62$.

With threshold $t$ there are $k=101-t$ stopping faces with average $\frac{t+100}{2}$, and each round fails with probability $\frac{t-1}{100}$. Solving $V=\frac{k}{100}\cdot \frac{t+100}{2}+\frac{t-1}{100}(V-1)$ gives

$V_{86}=87.33$, $V_{87}=87.357$, $V_{88}=87.31$, so stop at 87 or more. Consistency check: you keep any face above $V-1\approx 86.4$.

The interviewer wants to see structured thinking, not a closed form. A good approach:

• Your die $d$ tells you the jar is worth $d+3.5$ in expectation before any bidding.
• Each of the opponent’s bids is evidence about their die. Assume they play the same strategy as you (“you claim it’s optimal”).
• Write a rule per die value: bid up to a ceiling that depends on $d$ and on what their bids imply, and pass above it.
• One conservative strategy never bids above $d+1$ (the jar is at least $d+1$), so it can never lose money; then discuss how much expected profit it gives up.

This checks that you speak market-making language (bid, ask, width, “I’ll buy at…, sell at…”). It isn’t a Fermi problem with a deep answer. Give a central guess with a reason (“a coffee table plus a rack: about 5”), make the width reflect how unsure you are, and move sensibly after each trade.

Product of independent dice: $E=3.5\times 6.5=22.75$, with a wide spread (from 1 to 72), so show a wider market.

Maximum: $P(M\le m)=\min (\frac{m}{3},1)\min (\frac{m}{4},1)\min (\frac{m}{8},1)$, and $E[M]={\sum }_{m=0}^7(1-P(M\le m))=\frac{39}{8}=4.875$. Since they will trade against you on one side, centre on fair value and pick a width you’re comfortable losing half of.

• From the per-hole probabilities, compute the distribution of 10-throw scores for each candidate strategy (yours and theirs). It is a sum of independent throws, so it can be simulated or convolved.
• Identify the opponent’s strategy from the practice rounds, then choose the strategy that maximises your probability of beating it (not your expected score: a risky strategy can win more often against a safe opponent).
• Bet more when your win probability is well above 50%, along the lines of Kelly sizing.

• The fair coin alone guarantees 50 expected heads, so the game breaks even at worst. Exploring the unknown coins can only add value if their prior allows biases above $0.5$.
• This is a multi-armed bandit. Keep a posterior for each coin’s bias (a Beta distribution is natural), flip the coin with the best sampled bias (Thompson sampling) or the highest upper confidence bound, and update after every flip.
• Early flips explore; later flips exploit the best coin found. With only 100 flips, stop exploring fairly early.

• Each throw costs 1 chip and is worth $20\times$ (increase in your probability of ending closest).
• Estimate both distance distributions from observed throws: they are unknown, so early throws are partly exploration.
• If you are currently closest, passing puts pressure on them: they must pay to beat you. If you are behind, throw while the chance of beating the current best is above about 1 in 20 per chip (less if they will respond).

With $c=\mathrm{Corr}(X,Z)$ the determinant of the correlation matrix must be non-negative: $-c^2+1.44c-0.45\ge 0$, i.e. $c\in 0.72\pm \sqrt{0.19\times 0.36}$. Geometrically, correlations are cosines of angles: X is 25.8° from Y and Z is 36.9° from Y, so X and Z are between 11.0° and 62.7° apart.

Two insights:

• Treat ants as indistinguishable: a collision looks the same as two ants passing through. So after one minute the set of occupied positions is the same as at the start.
• Ants never pass each other, so their cyclic order is fixed and the labels are rotated by some amount. That rotation equals the net number of ants crossing a fixed point, which is (clockwise − anticlockwise) ants, mod $n$.

Everyone is home iff $2\cdot \#\text{cw}-n\equiv 0(\mathrm{mod}n)$: all clockwise, all anticlockwise, or (for even $n$) exactly half each. Count those configurations out of $2^n$.

Bayes with hypergeometric likelihoods:

so $P(B\mid \text{draw})=\frac{48}{112+48}=0.3$.

The shortcut “cancel one blue against one red and condition on a single blue” works only with replacement (it would give $1/3$). Without replacement, removing balls changes the bags differently.

Independent: $0.6\times 0.3=0.18$.

No assumptions: $P(\text{no rain})=1-P(A\cup B)$ and $\max (P(A),P(B))\le P(A\cup B)\le \min (1,P(A)+P(B))$, so $0.7\le P(A\cup B)\le 1$ and $0\le P(\text{dry})\le 0.3$.

Choosing 4 of 20 random points is the same as choosing 4 random points. The chords cross exactly when C and D separate A and B around the circle. Fix A; of the three equally likely positions of B in the cyclic order of the other three points, exactly one (B opposite A, i.e. ACBD or ADBC) separates C from D. So $1/3$. (Counting all 24 orderings: 8 of them cross.)

$P(\text{4-engine crash})=4p^3(1-p)+p^4$, $P(\text{2-engine crash})=p^2$. Setting them equal: $4p(1-p)+p^2=1\Rightarrow 3p^2-4p+1=0\Rightarrow p=\frac{1}{3}$ (or 1). Test $p=\frac{1}{4}$: 4-engine $\approx 0.051$ vs $0.0625$; at $p=\frac{1}{2}$: $0.3125$ vs $0.25$.

Let $X$ be the payout. Conditioning on the first flip, $X=\frac{1}{2}\cdot 1+\frac{1}{2}(X+1)$, so $X=2$.

Paying $2^n$: $E={\sum }_{n\ge 1}{2}^n{2}^{-n}=\sum 1=\infty$, the St Petersburg paradox. Nobody pays infinity: the counterparty can’t pay out huge amounts, and utility is concave. One defensible answer ignores outcomes rarer than 1 in 32, which caps the value at $5.

This is reservoir sampling. Take house 1 with probability 1. If house $i$ is replaced with probability $1/i$, then by induction each of the first $i$ houses is in memory with probability $1/i$: the newest with $1/i$, and each earlier one with $\frac{1}{i-1}\cdot \left(1-\frac{1}{i}\right)=\frac{1}{i}$.

Let $E_n$ be the answer for $n$ numbers. The first pick is 0 with probability $\frac{1}{n}$; otherwise it is uniform on $\mathrm{1..}n-1$ and leaves $\{0,\dots ,x-1\}$. A cleaner view: number $k$ is ever picked iff it is picked before all of $\mathrm{0..}k-1$, which has probability $\frac{1}{k+1}$. By linearity $E_n={\sum }_{k=0}^{n-1}\frac{1}{k+1}=H_n$. For $n=4$: $2.08$.

$t={\hat{\beta }}_1/\mathrm{se}({\hat{\beta }}_1)$ follows a $t_{N-2}$ distribution under ${\beta }_1=0$; $|t|>2$ is the usual threshold. For overfitting: penalise coefficients (L1, L2 or both), choose $\lambda$ by cross-validation, and judge on held-out data.

Keep a double-ended queue of (time, price) with prices increasing from front to back.

• New price: pop from the back while the back’s price ≥ the new price (they can never be the minimum again), then push the new one.
• Query: pop from the front while its time is older than 30 minutes; the front is the minimum.

Every price is pushed and popped at most once, so the amortised cost is $O(1)$.

Start from a nearby square: $\sqrt{49}=7$. One Newton step: $\sqrt{a^2+d}\approx a+\frac{d}{2a}=7+\frac{1}{14}\approx 7.071$. Optiver and other options firms test fast arithmetic like this, along with fractions and percentages, under time pressure.

Mean 27 minutes, sample standard deviation $\sqrt{430/4}\approx 10.4$. One-sided 95% needs $27+1.645\times 10.4\approx 44$ minutes, so leave by about 8:16 (8:15 to be safe).

The required buffer is $\mu +1.645\sigma$. Cutting $\mu$ by a minute saves 1 minute; cutting $\sigma$ by a minute saves 1.645 minutes.

• Exactly 1 out of place: impossible (if three letters are home, so is the fourth).
• Exactly 2: choose the pair to swap, $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$.
• Exactly 3: choose the fixed letter (4 ways) and derange the other three (2 ways): 8.
• All 4: the derangement number $D_4=9$. Check: $1+0+6+8+9=24=4!$.

Hits: $s+d+t+h=30$; bases: $s+2d+3t+4h=50$. Subtract: $d+2t+3h=20$.

(a) Maximise $s$ by minimising extra-base hits: $h=6,t=1$ uses 7 hits, so $s=23$.

(b) With $h=0$: $d+2t=20$, so $t=0,1,\dots ,10$: 11 combinations.

(c) Extra bases are $0.2x$, so $t$ runs from 0 to $0.1x$: $x/10+1$ combinations.

The outcomes fill the unit hypercube (volume 1). The region with $x_1+\cdots +x_n\le 1$ is a simplex: a triangle of area $\frac{1}{2}$ in 2D, a tetrahedron of volume $\frac{1}{6}$ in 3D, and in general volume $\frac{1}{n!}$.

Flip twice: HH, HT, TH are the three outcomes; on TT, start again.

$k$ flips give $2^k$ outcomes, so you need $2^k\ge n$: $k=\lceil {\log }_{2}n\rceil$ per attempt, rejecting the leftover outcomes.

For one $\frac{1}{3}$ event: flip; H means “no”. On T flip again: TH means “yes”, TT means start over. Then $E=1+\frac{1}{2}(1+\frac{1}{2}E)$, so $E=2$. This is optimal: it reads off the binary expansion $\frac{1}{3}=0.010101{\dots }_2$ one digit per flip.

Let $W_1$ and $W_2$ be the probability the ant about to move wins from distance 1 and 2. From distance 2 every move reaches distance 1, so $W_2=1-W_1$. From distance 1, of the mover’s 4 neighbours: 1 is the other ant (win), 2 are still adjacent to it, and 1 is opposite it. So

giving $W_1=\frac{3}{5}$ and $W_2=\frac{2}{5}$. A starts at distance 2: $\frac{2}{5}$.

$Y-X\sim \mathcal{N}(0,5)$. For $Z\sim \mathcal{N}(0,{\sigma }^2)$, $E|Z|=\sigma \sqrt{2/\pi }$ (twice the integral of $zf(z)$ over $z>0$). So $E|Y-X|=\sqrt{5}\sqrt{2/\pi }=\sqrt{10/\pi }$. Options traders know this as the straddle approximation: an at-the-money straddle is worth about $0.8\sigma \sqrt{T}$.

Choose which ace (4 ways) and 17 non-aces from 48, out of all $\left(\genfrac{}{}{0ex}{}{52}{18}\right)$ hands: $\frac{4\left(\genfrac{}{}{0ex}{}{48}{17}\right)}{\left(\genfrac{}{}{0ex}{}{52}{18}\right)}\approx 0.398$. (The grouping into sets of three doesn’t matter for this count. If the question means “exactly one of the six sets holds an ace”, say which reading you are answering.)

Whenever someone has to choose randomly, seat 1 and seat 100 are equally likely to be chosen, and the first of those two to be taken decides everything: if seat 1 goes first, everyone else (including 100) gets their seat; if seat 100 goes first, passenger 100 doesn’t. By symmetry each happens with probability $\frac{1}{2}$.

• Sort and take the top $k$: $O(n\log n)$.
• Keep a min-heap of size $k$: for each element, if it beats the heap’s minimum, replace it. $O(n\log k)$ time and $O(k)$ memory; good for streams.
• Heapify everything ($O(n)$) and pop $k$ times: $O(n+k\log n)$.
• Quickselect to find the $k$-th largest, then partition: $O(n)$ on average.

Count occurrences of each value in a hash map. For each distinct value $v$, add $\text{count}[v]\cdot \text{count}[m-v]$, handling $v=m-v$ with $\left(\genfrac{}{}{0ex}{}{\text{count}[v]}{2}\right)$ and counting each unordered pair once. Linear time. (Or single pass: for each element, add how many times $m-x$ has been seen so far, then record $x$.)

Walk forwards keeping the lowest price seen so far. At each price, the best sale today is price − minimum; keep the largest. One pass, $O(n)$ time, $O(1)$ memory. (Walking backwards with a running maximum works the same way.)

For centred data, $\beta =\frac{⟨X,Y⟩}{\Vert X{\Vert }^2}$ and ${\beta }^{\prime }=\frac{⟨X,Y⟩}{\Vert Y{\Vert }^2}$, so $\beta {\beta }^{\prime }=\frac{⟨X,Y{⟩}^2}{\Vert X{\Vert }^2\Vert Y{\Vert }^2}={\cos }^2\theta ={\rho }^2$. Cauchy–Schwarz gives $⟨X,Y{⟩}^2\le \Vert X{\Vert }^2\Vert Y{\Vert }^2$.

$E[a_{i+1}-a_i]=0$. By independence $\mathrm{Var}(a_{i+1}-a_i)={\sigma }^2+{\sigma }^2=2{\sigma }^2$. A detail worth adding: consecutive differences share a term, $\mathrm{Cov}(a_{i+1}-a_i,a_i-a_{i-1})=-{\sigma }^2$, so they are negatively correlated. Differencing white noise creates fake mean reversion, a classic trap with price data.

$Y-3X\sim \mathcal{N}(0,10)$ is symmetric around 0, so $P(Y-3X>0)=\frac{1}{2}$. Or: the joint density of $(X,Y)$ is radially symmetric, and the line $y=3x$ through the origin cuts it in half.

Use radial symmetry: probability is proportional to angle. The condition $X>0$ is a half-plane (angle $\pi$). Within it, $Y>3X$ is the wedge between the line $y=3x$ (angle $\arctan 3$) and the positive $y$-axis (angle $\pi /2$), of angle $\pi /2-\arctan 3=\arctan \frac{1}{3}$. Answer: $\arctan (1/3)/\pi$.

If the first person is at percentile $p$, each later person is taller with probability $1-p$, so the expected wait is $\frac{1}{1-p}$. The percentile is Uniform(0, 1) whatever the height distribution, so the answer is ${\int }_0^1\frac{dp}{1-p}=\infty$. The rare chance that the first person is one of the tallest people alive makes the expectation diverge.

Let $f(x)$ be the expected draws to exceed $x$ (for $0\le x\le 1$). Then $f(x)=1+{\int }_0^{x}f(x-t)dt=1+{\int }_0^{x}f(u)du$, so $f^{\prime }=f$ with $f(0)=1$, giving $f(x)=e^x$ and $f(1)=e$. Alternatively: $P(\text{more than }n\text{ draws needed})=P(\text{sum of }n\le 1)=\frac{1}{n!}$ (the Akuna question), and $E={\sum }_{n\ge 0}\frac{1}{n!}=e$.

Write each bottle’s number in binary with 10 digits; rat $i$ drinks from every bottle whose $i$-th digit is 1. The set of dead rats spells out the poisoned bottle’s number. So $n$ rats handle $2^{10}=1024$, and in general $2^n$.

With two hours, use base 3: digit 1 means “drink in hour 1”, digit 2 “drink in hour 2”, 0 “never”. Each rat then reports one of three outcomes (dies in hour 1, dies in hour 2, survives): $3^n$ bottles. With $k$ hours, $(k+1{)}^n$.

An attempt of length $L$ (that is, $L-1$ evens then a 1) has probability ${\left(\frac{1}{2}\right)}^{L-1}\frac{1}{6}$. Attempts that end in 1 rather than 3/5 have total probability ${\sum }_L{\left(\frac{1}{2}\right)}^{L-1}\frac{1}{6}=\frac{1}{3}$. So the kept sequence has $P(L)={\left(\frac{1}{2}\right)}^{L-1}\frac{1}{6}/\frac{1}{3}={\left(\frac{1}{2}\right)}^L$: geometric with mean 2.

The tempting answer, “ignore 3 and 5, so it’s a 1-in-4 chance each roll and the length is 4”, is wrong because throwing out long sequences (which had more chances to hit a 3 or 5) biases the kept ones towards being short.

A and B play either once or never, so $P(\text{meet})$ equals the expected number of A-vs-B games. A knockout with $n$ teams has exactly $n-1$ games, and by symmetry each game is equally likely to be any of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs. By linearity:

This indicator trick (“probability = expected count of something that happens 0 or 1 times”) is worth remembering.

A sock labelled 1 can only pair with another 1 or a 2. Either the two 1s are paired together (probability $\frac{1}{2n-1}$), leaving the game on $n-1$ pairs; or both 1s are paired with the two 2s (probability $\frac{2}{(2n-1)(2n-3)}$), leaving $n-2$ pairs. Any other pairing of the 1s eventually strands a sock. Hence the recursion.

For $n=3$: $P_3=\frac{1}{5}+\frac{2}{15}=\frac{1}{3}$. Direct check: of the 15 ways to pair 112233, the winners are {11,22,33}, two ways of {11,23,23} and two ways of {12,12,33}: 5 out of 15. Next values: $P_4=11/105$, $P_5=1/45$.

Expected return per $1 on the side with win probability $p$ at even odds is $2p-1$. With $p=\frac{1}{3}$ for the game, you want the other side, with $p=\frac{2}{3}$ and edge $\frac{1}{3}$.

For repeated bets, maximise long-run log wealth: the Kelly fraction is $f^{\ast }=\frac{p}{a}-\frac{q}{b}$ for losing fraction $a$ and winning fraction $b$ of the stake. With $a=b=1$, $f^{\ast }=\frac{2}{3}-\frac{1}{3}=\frac{1}{3}$.

Condition on red faces, not cubes. There are 54 red faces in total ($6\times 9$). Corner cubes contribute $8\times 3=24$ of them. Each red face is equally likely to be the one on top, so $\frac{24}{54}=\frac{4}{9}$.

Let $P_x$ be your win probability holding $x$ dollars ($x=\mathrm{0..3}$), with $P_0=0$ and $P_3=1$. Then $P_1=\frac{2}{3}{P}_2$ and $P_2=\frac{2}{3}+\frac{1}{3}{P}_1$. Substituting, $P_1=\frac{4}{9}+\frac{2}{9}{P}_1$, so $P_1=\frac{4}{7}$. (Gambler’s ruin: $\frac{1-r}{1-r^3}$ with $r=q/p=\frac{1}{2}$.)

The current price is the expected value: $10=0.5(0.4\cdot 5)+0.5(0.8\cdot 15+0.2x)=1+6+0.1x$, so $x=30$.

The call struck at 22 pays only in the $30 outcome, which has probability $0.5\times 0.2=0.1$: worth $0.1\times (30-22)=\$0.80$.