Hudson River Trading interview questions

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$.

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

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}$.

A virtual function call in C++ adds overhead from an indirect branch, loss of inlining and subsequent compiler optimisations, and the per‑object vptr.

Function pointer alternative – Replacing the virtual method with a stored function pointer removes the vtable indirection but still requires an indirect call; the call cost itself is unchanged. Inlining remains impossible unless the compiler can prove the pointer value at compile time. For truly dynamic dispatch, performance is on par with virtual functions, while the code loses type safety and polymorphic extensibility.

Templates (CRTP / static polymorphism) – By resolving the target type at compile time, templates enable direct calls that are fully inlineable. This eliminates all dispatch overhead and can yield large speedups for small, frequently‑called operations. The trade‑off is the loss of runtime polymorphism: all concrete types must be known at compile time. Template instantiation may also increase binary size and compilation time.

Performance verdict – In hot inner loops where the type is statically known, templates consistently outperform virtual functions. Function pointers rarely provide a meaningful advantage; they replace one indirection with another while sacrificing design clarity. In most real‑world code, virtual function overhead is dwarfed by other costs (memory latency, I/O, algorithmic complexity) and modern branch predictors hide much of the remaining penalty.

Conclusion – Virtual functions remain the right default for runtime polymorphism. They should be replaced with templates only when profiling identifies a hot virtual call site and compile‑time dispatch is feasible. The flexibility and maintainability they offer are well worth their overhead in the vast majority of code.