Five Rings interview questions

Coupon Collector's Problem

High-level idea. Decompose the total waiting time into independent geometric stages, then apply linearity of expectation.

Stage decomposition

Let $T$ be the total number of rolls of a fair $N$-sided die needed to observe every face at least once. Define stage $k$ ($k = 1, \ldots, N$) as the period that begins the moment the $(k{-}1)$-th distinct face was first seen and ends when the $k$-th distinct face is first seen. Writing $T_k$ for the number of rolls in stage $k$,

Distribution of each stage

At the start of stage $k$, exactly $k-1$ faces have been observed. Each roll independently reveals a previously unseen face with probability

Hence $T_k \sim \operatorname{Geometric}(p_k)$ (number of trials until first success), so

Closed-form expected value

By linearity of expectation,

Reindexing with $j = N-k+1$ (as $k$ runs $1 \to N$, $j$ runs $N \to 1$):

where $H_N = \displaystyle\sum_{j=1}^{N} \frac{1}{j}$ is the $N$-th harmonic number.

Numerical evaluation for $N = 100$

Using the Euler–Maclaurin asymptotic expansion

with $\gamma = 0.57721566490153\ldots$ (Euler–Mascheroni constant):

Therefore,

Rounded to the nearest integer:

Let $N$ be the number of coin flips until the first heads appears. Since the coin is fair, $N$ follows a geometric distribution with success probability $1/2$: $P(N = n) = (1/2)^n$ for $n = 1, 2, 3, \dots$ (the first $n-1$ flips are tails and the $n$th flip is heads). The payout when $N = n$ is $2^n$ dollars. The expected value of the payout is

Since the expected value is infinite, the game does not have a finite fair value. Per the problem instructions, output $-1$.

High-level idea

Model the process as a Markov chain with two transient states tracking the current "run" of consecutive 1s. Set up first-step equations and solve the $2\times 2$ linear system.

States and equations

Let $p = \tfrac{1}{6}$ be the probability of rolling a 1. Define:

• $S_0$: start, or the last roll was not a 1.
• $S_1$: the last roll was a 1 (one consecutive 1 in progress).

Let $\mu_0,\mu_1$ be the expected number of additional rolls needed to reach absorption (two consecutive 1s) from each state.

From $S_0$ — one roll is used; with probability $\tfrac{1}{6}$ we move to $S_1$, with probability $\tfrac{5}{6}$ we remain in $S_0$:

From $S_1$ — one roll is used; with probability $\tfrac{1}{6}$ we finish (0 more rolls), with probability $\tfrac{5}{6}$ we return to $S_0$:

Solving the system

Rearranging the first equation:

Substituting $\mu_1 = 1 + \tfrac{5}{6}\mu_0$:

Check: $\mu_1 = 1 + \tfrac{5}{6}(42) = 36$, and $6 + 36 = 42$. ✓

Final answer

The expected number of rolls is $\boxed{42}$.

Idea

Work with the complement: a triple fails the triangle inequality if and only if one side is at least as large as the sum of the other two. The three failure events turn out to be mutually exclusive, so the failure probability is simply $3P(A)$ for any one of them.

Setup

Let $X, Y, Z \overset{\text{iid}}{\sim} \text{Uniform}[0,1]$. Define the failure events

Mutual Exclusivity of $A$, $B$, $C$

Suppose $A \cap B$ occurs: $X+Y \le Z$ and $X+Z \le Y$. Adding these inequalities gives $2X + Y + Z \le Y + Z$, hence $X \le 0$. Since $X \ge 0$ a.s., this forces $X = 0$, an event of probability zero. By symmetry, every pairwise intersection has measure zero, so $A$, $B$, $C$ are mutually exclusive a.s. Combined with symmetry of the joint distribution,

Computing $P(A)$

Condition on $Z = z$. The event $\{X + Y \le z\}$ within $[0,1]^2$ traces the right triangle $\{x \ge 0,\, y \ge 0,\, x+y \le z\}$, which has area $z^2/2$. Therefore

Final Answer

We have 8 points on a circle, so there are $\binom{8}{2}=28$ chords in total. Choosing 4 chords uniformly at random gives $\binom{28}{4}$ equally likely outcomes.

For the 4 chords to form a convex quadrilateral, their union must be exactly the boundary of that quadrilateral. Because the points lie on a circle, any 4 distinct points determine a convex quadrilateral whose sides are the chords connecting consecutive points in cyclic order. Thus a favorable set of 4 chords corresponds precisely to choosing 4 of the 8 points and taking the four boundary chords of that set. There are $\binom{8}{4}=70$ ways to choose the points, and each yields exactly one favorable 4‑chord set. No other set of 4 chords can form a convex quadrilateral, since any quadrilateral must have four distinct vertices, and on a circle the only non‑self‑intersecting 4‑cycle on four points is the boundary cycle.

Hence the probability is

We have 15 boys and 10 girls, totaling 25 students. The students line up uniformly at random. We want the expected number of adjacent positions where one is a boy and the other is a girl (order BG or GB).

Let $X$ be the number of adjacent boy-girl pairs. For each adjacent pair of positions $(i, i+1)$ with $i = 1,\dots,24$, define an indicator $I_i$ that the two students at those positions are of opposite sexes. Then $X = \sum_{i=1}^{24} I_i$, and by linearity of expectation,

By symmetry, the probability is the same for every adjacent pair; denote it by $p$. Hence $\mathbb{E}[X] = 24 \cdot p$.

Now compute $p$. There are $25 \times 24$ equally likely ordered assignments of two distinct students to the two positions. Favorable cases are (boy, girl) and (girl, boy). There are $15 \times 10 = 150$ ways to choose a boy then a girl, and $10 \times 15 = 150$ ways to choose a girl then a boy, for a total of $300$ favorable ordered pairs. Thus

Alternatively, $\Pr(\text{boy then girl}) = \frac{15}{25} \cdot \frac{10}{24} = \frac{1}{4}$, and $\Pr(\text{girl then boy}) = \frac{10}{25} \cdot \frac{15}{24} = \frac{1}{4}$, so $p = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$.

Therefore,

The key insight is that when two ants meet and reverse direction, the system is equivalent to the ants passing through each other without interaction, because the ants are indistinguishable. Under this "pass-through" model, each ant simply continues in its original direction forever. Therefore, the number of ants that reach Priya's end equals the number of ants that were initially moving leftward (toward Priya), and the number that reach Theo's end equals the number initially moving rightward (toward Theo).

Initially, all 40 ants at Priya's end move rightward (toward Theo), and all 80 ants at Theo's end move leftward (toward Priya). Under the pass-through equivalence, the ants that reach Priya are those that started at Theo's end and moved leftward: 80 ants. The ants that reach Theo are those that started at Priya's end and moved rightward: 40 ants. Thus $x = 80$, $y = 40$, and

More formally, let $x$ be the number reaching Priya and $y$ the number reaching Theo. Under the pass-through model, each ant's trajectory is a straight line from its start to the opposite end. Since all ants move at the same speed, the number reaching each end is exactly the number that started at the opposite end. Hence $x = 80$, $y = 40$, and the difference is $40$.

Let the statements be numbered $1,2,\dots,100$. Statement $k$ says: "at most $k-1$ of these $100$ statements are true."

Let $T$ be the total number of true statements. For statement $k$ to be true, we must have $T \le k-1$; for it to be false, $T > k-1$. Hence statement $k$ is true exactly when $k \ge T+1$.

Thus the true statements are those with indices $T+1, T+2, \dots, 100$. The number of such statements is $100 - T$. But this number must equal $T$ itself, because $T$ is the total number of true statements. Therefore:

Check: If $T=50$, then statements $51$ through $100$ are true (50 statements). Statement $51$ says "at most $50$ are true" — true because exactly $50$ are true. Statement $50$ says "at most $49$ are true" — false because $50 > 49$. All statements $1$ through $49$ are false because each claims "at most $k-1$ are true" with $k-1 \le 48$, but $50 > k-1$. All statements $52$ through $100$ are true because each claims "at most $k-1$ are true" with $k-1 \ge 51$, and $50 \le k-1$. Hence exactly $50$ statements are true, consistent with $T=50$.

Thus the answer is $50$.

Let $q_k$ be the probability that the drunkard eventually steps onto the precipice (ruin) when he is currently $k$ paces from the edge ($k\ge 0$). The precipice is at $k=0$, so $q_0=1$. We want the survival probability $1-q_1$.

For $k\ge 1$, condition on the first step:

Multiply by $3$ and rearrange to obtain the homogeneous linear recurrence

The characteristic equation is $2r^2-3r+1=0$, which factors as $(2r-1)(r-1)=0$, giving roots $r=1$ and $r=\frac12$. Hence

Boundary conditions.

• At $k=0$: $q_0 = 1 \implies A + B = 1$.
• As $k\to\infty$, the walk has a positive drift away from the edge (each step has expected change $+\frac13$). Therefore the probability of ever hitting $0$ from far away tends to $0$, i.e. $\lim_{k\to\infty}q_k = 0$. This forces $A=0$, and consequently $B=1$.

Thus $q_k = \big(\frac12\big)^k$. In particular, the ruin probability starting one pace away is $q_1 = \frac12$. The probability that he never goes over the edge is

Let $M$, $T$, $W$ be the events that Monday, Tuesday, Wednesday produce a matching pair, respectively. We want

1. $P(M^c)$. Total ways to choose $2$ socks from $10$: $\binom{10}{2}=45$. Matching pairs: $5$ (one per color). So $P(M)=5/45=1/9$, hence

2. $P(T^c \mid M^c)$. After a non‑matching Monday, two socks of different colors are removed. The remaining $8$ socks consist of $3$ colors with $2$ socks each and $2$ colors with $1$ sock each. Total pairs from $8$: $\binom{8}{2}=28$. Only the three colors with $2$ socks can produce a matching pair, so $3$ matching pairs. Thus $P(T\mid M^c)=3/28$ and

3. $P(W \mid M^c \cap T^c)$. After Monday and Tuesday are both non‑matching, the composition of the remaining $6$ socks depends on how Tuesday's non‑matching pair was formed. Starting from the Monday state ($3$ colors with $2$ socks, $2$ colors with $1$ sock), Tuesday's non‑matching pair can be of three types:

• Case A: Both socks from the $2$-sock colors. Number of ways: $\binom{3}{2}\cdot2\cdot2 = 12$. Resulting state: $1$ color with $2$ socks, $4$ colors with $1$ sock. Probability of a match on Wednesday: $\frac{1}{\binom{6}{2}} = \frac{1}{15}$.
• Case B: One sock from a $2$-sock color and one from a $1$-sock color. Number of ways: $3\cdot2\cdot2\cdot1 = 12$. Resulting state: $2$ colors with $2$ socks, $2$ colors with $1$ sock, $1$ color with $0$ socks. Probability of a match on Wednesday: $\frac{2}{15}$.
• Case C: Both socks from the two $1$-sock colors. Number of ways: $1$. Resulting state: $3$ colors with $2$ socks, $2$ colors with $0$ socks. Probability of a match on Wednesday: $\frac{3}{15} = \frac15$.

Total non‑matching pairs on Tuesday: $12+12+1 = 25$, so the conditional probabilities of the cases given $T^c$ are $\frac{12}{25},\frac{12}{25},\frac{1}{25}$. Hence

4. Multiply.

Thus the desired probability is $\boxed{\frac{26}{315}}$.

(One can verify by counting all sequences: total sequences $\binom{10}{2}\binom{8}{2}\binom{6}{2}=18900$, favorable sequences $5\cdot24\cdot13=1560$, giving the same fraction.)

Idea

Track the game state as the longest suffix of the flip sequence that is a prefix of either target pattern. This yields a small Markov chain whose first-step equations determine the win probability exactly.

States and Transitions

Target patterns: Player 1 wins on $HTH$; Player 2 wins on $HHT$.

The transient states are $\{\varepsilon,\, H,\, HH,\, HT\}$, where $\varepsilon$ denotes no useful suffix (start, or after a progress-resetting tail).

Remark on $HH \xrightarrow{H} HH$: after any run of heads, the longest suffix that prefixes a target is still $HH$ (the length-2 prefix of $HHT$).

System of Equations

Let $p_s$ denote the probability that Player 1 wins from state $s$.

Equation (3) reflects that $HH$ is a trap: every additional $H$ keeps the game in $HH$, and the inevitable first $T$ completes $HHT$, so Player 1 cannot win from $HH$.

Solution

Substituting $(3)$ into $(2)$:

Combined with $(1)$, we have $p_{\varepsilon} = p_H = \tfrac{1}{2}p_{HT}$. Substituting into $(4)$:

The game begins in state $\varepsilon$, so Player 1 wins with probability $\dfrac{1}{3}$.

This is a classic "jeep problem" (desert crossing) variant. The tanker starts with $3000$ gallons at Port A, must travel $1000$ miles to Port B, loses $1$ gallon per mile, and has capacity $1000$ gallons. The goal is to maximize delivered oil.

Key insight: The optimal strategy uses intermediate depots and shuttles oil forward in stages, each stage moving a certain amount of oil a certain distance while consuming fuel for round trips. The number of trips decreases by one each stage.

Let $D = 1000$ miles, capacity $C = 1000$ gallons, initial fuel $F = 3000$ gallons. Consumption is $1$ gallon per mile.

General principle: To move $n$ full loads (i.e., $n \times 1000$ gallons) a distance $d$, you make $n$ forward trips and $n-1$ return trips, consuming $(2n-1)d$ gallons. The amount delivered forward is $nC - (2n-1)d$.

Stage 1: Start with $3000$ gallons at A, i.e., $n_1 = 3$ loads. Move forward distance $d_1$ such that after shuttling we have exactly $n_2 = 2$ loads ($2000$ gallons) at the next depot. Fuel consumed: $(2\cdot3-1)d_1 = 5d_1$. Remaining: $3000 - 5d_1 = 2000 \Rightarrow d_1 = 200$ miles.

Stage 2: At mile $200$, we have $2000$ gallons ($n_2 = 2$ loads). Move forward distance $d_2$ to reduce to $1$ load ($1000$ gallons). Fuel consumed: $(2\cdot2-1)d_2 = 3d_2$. Remaining: $2000 - 3d_2 = 1000 \Rightarrow d_2 = 333\frac{1}{3}$ miles.

Stage 3: At mile $200 + 333\frac{1}{3} = 533\frac{1}{3}$, we have $1000$ gallons ($n_3 = 1$ load). Drive directly to B, which is $1000 - 533\frac{1}{3} = 466\frac{2}{3}$ miles away. Fuel consumed: $466\frac{2}{3}$ gallons. Delivered: $1000 - 466\frac{2}{3} = 533\frac{1}{3}$ gallons.

Thus the maximum deliverable is $533\frac{1}{3}$ gallons, which rounds to $533$ gallons.

Verification: Total fuel consumed = $5\times200 + 3\times333\frac{1}{3} + 1\times466\frac{2}{3} = 1000 + 1000 + 466\frac{2}{3} = 2466\frac{2}{3}$ gallons, matching $3000 - 533\frac{1}{3}$. Total distance traveled = same sum, confirming consumption rate.

The average speed is total distance divided by total time, not the arithmetic mean of the speeds. Let the length of one lap be $d$ miles. The times for each lap are:

• Lap 1: $t_1 = \frac{d}{100}$ hours
• Lap 2: $t_2 = \frac{d}{150}$ hours
• Lap 3: $t_3 = \frac{d}{200}$ hours

Total distance: $3d$ miles. Total time: $t_1 + t_2 + t_3 = d\left(\frac{1}{100} + \frac{1}{150} + \frac{1}{200}\right)$.

Hence the average speed $v$ is

Compute the denominator using a common denominator of $600$:

Therefore,