Statistical and Simulation Coding

Throw darts uniformly at the unit square and count how many land inside the quarter circle, where x² + y² ≤ 1. Because the darts are uniform, that fraction estimates the ratio of areas, which is pi/4, so four times the fraction estimates pi. I would compare squared distances rather than taking square roots, and seed the generator for reproducibility.

For the precision question: each dart is Bernoulli with p = pi/4, so the estimator 4·p̂ has standard error 4·√(p(1−p)/n). Setting 1.96 standard errors equal to 0.01 and solving gives about 103,600 darts. Two decimals is cheap, but four would need roughly 4.1 billion, because the error only falls as 1/√n — which is the real answer to why nobody computes pi this way.

Flip it twice. HT and TH both have probability p(1−p) — identical regardless of p, because each contains exactly one head and one tail. So I map HT to 1, TH to 0, and discard HH and TT, repeating until I get a differing pair. The bias cancels by symmetry rather than being estimated and corrected, which is why it is exact rather than approximate.

The cost is the natural follow-up: a pair is usable with probability 2p(1−p), so the expected flips per output bit is 1/(p(1−p)). That is 4 at p = 0.5 and over 21 at p = 0.05, so the method is unbiased for every p but becomes very slow as the coin approaches deterministic. I would verify by generating tens of thousands of bits at several biases and checking the fraction of ones is 0.5 within sampling error each time.

Six for HH, four for HT. They differ because of what a failure costs. Waiting for HT with an H in hand, a second H is not a setback — I still have an H and I am still one T from finishing. Waiting for HH with an H in hand, a T destroys all progress and returns me to the start. HH is self-overlapping, so it can be knocked back; HT cannot.

Formally, first-step analysis. Let a be the expected flips from scratch and b the expected flips given the last flip was an H. For HT: b = 1 + ½(0) + ½b gives b = 2, then a = 1 + ½b + ½a gives a = 4. For HH the second equation becomes b = 1 + ½(0) + ½a, because failure resets to the start rather than staying in state H, and that single substitution yields a = 6. Simulating 150,000 sequences gave 5.99 and 4.01.

Two calls give 25 equally likely outcomes via 5·first + second. Seven does not divide 25, so no direct mapping can be uniform. I keep outcomes 0 through 20 — 21 values, exactly three per remainder class mod 7 — and reject 21 through 24, retrying from scratch. Rejection is what makes it exactly uniform, not an inefficiency to be optimised away.

Each attempt uses 2 calls and succeeds with probability 21/25, so the number of attempts is Geometric with mean 25/21 and the expected cost is 50/21, about 2.38 calls to rand5 per output. The important thing not to do is salvage the rejected values into the next attempt: that correlates consecutive attempts and breaks uniformity in a way that casual testing will not reveal.

The obvious version swaps each position with a uniformly random position from the whole array. That makes n independent choices from n options, so there are nⁿ equally likely execution paths, but only n! possible orderings. For all orderings to be equally likely, n! would have to divide nⁿ evenly. For n = 3 that is 6 into 27, which fails, so some orderings are strictly more likely. That counting argument settles it without any simulation.

The fix is Fisher-Yates: walk from the end and swap position i with a random index drawn from 0 to i inclusive. The choice counts are then n, n−1, down to 1, whose product is exactly n!, giving one execution path per ordering. The inclusive bound matters — excluding i produces a different biased shuffle in which no element can stay put. I confirmed both empirically: over 120,000 shuffles of three elements, Fisher-Yates was flat and the naive version was visibly skewed.

Twenty-three. I compute it through the complement, because "at least one shared birthday" directly would require inclusion-exclusion over pairs, triples and so on. P(all distinct) is the product of (365−i)/365 for i from 0 to k−1, and the answer is one minus that. At k = 23 it gives 0.5073.

The reason 23 feels too small is that intuition anchors on your birthday, which is only 22 comparisons. The question is about any pair, and 23 people form C(23,2) = 253 pairs. Opportunities grow quadratically in the number of people while intuition tracks them linearly. I would sanity-check with a simulation: 60,000 simulated rooms gave 0.5049, comfortably within sampling error of the exact value.

Five thirteenths, about 0.385. I define an indicator variable for each of the five positions being an ace. Each position is equally likely to hold any of the 52 cards, so each indicator has expectation 4/52, and the total is 5 × 4/52.

The dependence is irrelevant because linearity of expectation holds regardless of independence — E[X+Y] = E[X] + E[Y] always, and the proof never uses independence. The draws genuinely are dependent, and that dependence would matter if I were computing the variance, where a covariance term appears. This is the single most useful technique in card problems, because it converts an intimidating without-replacement setup into arithmetic.

n·H(n), where H(n) is the n-th harmonic number. I decompose the total wait into stages: stage i runs from holding i distinct coupons to holding i+1. During that stage a draw is new with probability (n−i)/n, so the stage length is Geometric with mean n/(n−i). Summing over stages and applying linearity gives n times the sum of 1/1 through 1/n.

Since H(n) grows like ln n, the total grows like n ln n — meaningfully worse than linear. The intuition the formula captures is that the last coupon alone takes n draws on average, so a large share of the effort goes into hunting the final one. For a six-sided die it is 15.7 draws; simulation gave 14.68.

Reservoir sampling. Keep the first k items. For each later item at index i, draw j uniformly from 0 to i, and if j is less than k, replace the incumbent at position j. One pass, O(k) memory, and no need to know the stream length in advance.

The proof is the interesting part. Item i is accepted on arrival with probability k/(i+1). It then survives each later arrival m with probability m/(m+1), since that arrival evicts a specific incumbent with probability 1/(m+1). Multiplying those survival terms telescopes to (i+1)/n, and k/(i+1) times (i+1)/n is k/n — independent of i, so every item is equally likely regardless of when it arrived.

Switch; it wins two thirds of the time. My initial pick is correct with probability 1/3. If it was correct, switching loses. If it was wrong — probability 2/3 — then the host, who knows where the car is, is forced to open the only other goat door, so the remaining door must hold the car and switching wins. Switching therefore wins exactly when my first pick was wrong.

What would change the answer is the host's rule. If the host opened an unpicked door at random and it happened to reveal a goat, the probability really would be 1/2 and switching would not matter, because no information was deliberately transferred. So I would confirm the host's constraint before answering. This is also the classic simulation trap: coding a random-opening host returns 0.5 and appears to disprove the correct answer, when in fact it simulated a different game.

Not until I have checked that the gap is consistent with sampling error rather than eyeballing it. The difference here is 0.0008. With n trials the standard error is about √(p(1−p)/n), which at p = 1/3 and n = 100,000 is roughly 0.0015. The observed gap is well under one standard error, so the two agree and I am finished.

Had the gap been, say, 0.01 — around seven standard errors — I would treat that as a bug rather than noise, and the most likely culprit is the simulation encoding a subtly different process rather than the algebra being wrong. The general habit is that "close enough" should be a computed comparison against the standard error, not an impression.

Right when the exact computation is intractable or the process is easier to describe than to analyse: high-dimensional integrals, complex dependency structures, queueing and inventory systems, or anything with awkward conditional logic. Its headline property is that the 1/√n error rate does not depend on the number of dimensions, which is exactly where deterministic quadrature falls apart.

Wrong when a closed form exists — it will be exact, instant, and it will not mislead you with three plausible digits. Also wrong when high precision is required, since each additional digit costs a hundredfold more samples, and wrong for estimating extremely rare events, where almost every sample is wasted and you need importance sampling instead. In an interview I would give the exact answer where one exists and use simulation to confirm it, because that combination is stronger than either alone.