Coupon Collector Interview Questions: Expected Draws, Unequal Odds, and Stopping Rules

Coupon collector interview questions ask how long it takes to see every type, not how many different types you expect after a fixed number of draws. For n equally likely types sampled independently with replacement, the expected completion time is n*H_n, where H_n is the harmonic sum. Unequal odds require more state, and an expected time is not a deadline guarantee.

Define the stopping rule and the sampling model before choosing a formula. This guide develops an original unequal-odds example, a small exact calculation, and a reproducible simulation that keeps unfinished runs visible.

Primary academic sources support the theory; the worked calculations and code below are our original interview rehearsal. No employer-specific question frequency or hiring outcome is claimed.

What does one draw mean, and when do you stop?

Our baseline experiment has a known finite set of types. Each draw produces one type, the probabilities stay fixed, and draws are independent. Replacement allows repeats. The stopping time T is the first draw count at which every required type has appeared.

The Random Services textbook defines the classical replacement-sampling model and collection of a specified number of distinct values. In an interview, make the counting convention explicit: the successful final draw is included, and an empty collection is complete before any draw.

Ask whether the task requires all types, any m distinct types, a named subset, or several copies of each type. Those are different stopping conditions. “Find the expected number of samples” does not identify which one the interviewer intends.

Our first diagnostic example contrasts two bags. A bag containing one copy of each of six labels, drawn without replacement, finishes after six draws. Independent uniform draws with replacement can repeat labels indefinitely and have a larger finite expectation. The word “random” alone does not make the models interchangeable.

Why does the uniform answer contain a harmonic sum?

MIT's coupon collector tutorial uses waiting stages and linearity of expectation. With k distinct types already seen, a new type arrives with probability (n-k)/n; the next stage therefore has expected length n/(n-k).

Adding the n stages gives 1 + n/(n-1) + ... + n = n*H_n. For six types the mean is 14.7 draws. Linearity justifies summing expectations; it should not be described as a rule that requires independent summands.

For our rehearsal, read the stages aloud rather than only presenting the final sum. The first draw always adds a type. When five of six types have been seen, only one face advances the collection and the expected remaining wait is six draws. The later stages carry more waiting time because success becomes less likely.

That last sentence is about an expectation, not a fixed six-draw countdown. If five unsuccessful draws occur while waiting for the final face, the next draw still succeeds with probability 1/6. Under the stated model, previous failures do not make the missing face “due.”

How does collecting only part of the set change the answer?

Our partial-collection extension stops after any m distinct types, with 0 <= m <= n. Keep only the first m waiting stages: E[T_m] = sum(n/(n-k), k=0,...,m-1).

For six uniform types, collecting any three takes 1 + 6/5 + 6/4 = 3.7 draws on average. Collecting three particular named types is a different task: draws of the other three types do not satisfy the target. State which requirement you are solving before reusing the partial formula.

Boundary checks make this extension useful. Collecting zero types takes zero draws; one type takes one draw; collecting all six recovers 14.7. A formula that fails one of those checks usually has an indexing or stopping-definition error.

Do not multiply the all-types expectation by m/n. The stages have different expected lengths, so the first half of the distinct types does not consume half the expected completion time. The original three-of-six example gives a concrete counterexample to that shortcut.

Why is a distinct-count state insufficient for unequal odds?

The Boneh and Hofri survey treats fixed, potentially unequal type probabilities and different collection targets. The uniform case hides the identity of the seen types because every set of the same size leaves the same probability mass missing.

Our original three-type example uses probabilities A=0.5, B=0.3, and C=0.2. After exactly one distinct type has appeared, the expected wait for the next new type depends on its identity. If A was seen, the missing mass is 0.5 and the next-stage mean is 2. If C was seen, the missing mass is 0.8 and the mean is 1.25.

Both states contain one distinct type, but they are not equivalent. A count-only recurrence that assigns one transition probability to both states loses information. Track the seen set or another representation that preserves the relevant remaining probabilities.

Our two-type counterexample is even smaller: A appears with probability 0.99 and B with 0.01. Let their first-arrival times be T_A and T_B. Completion is their maximum, so max(T_A,T_B) = T_A + T_B - min(T_A,T_B). One of the two types necessarily appears on the first draw, making the minimum exactly one.

The resulting expectation is 1/0.99 + 1/0.01 - 1, approximately 100.010101. The equal-odds two-type answer is 3. Averaging the two probabilities first destroys the rare-type constraint rather than approximating it responsibly.

Compute a small unequal-odds case with first-step states

Define E(S) as the expected additional draws when the seen set is S. A draw always costs one. A repeated type returns to S; a missing type moves to a larger set. Rearranging that first-step equation gives:

E(S) = [1 + sum(p_i * E(S union {i}), i missing)]
       / sum(p_i, i missing)
E(all types) = 0

The denominator is missing probability mass, not the number of missing labels. Our exact-state implementation uses a bitmask and caches the expectation for each seen set. It is suitable for small examples and moderate floating-point probabilities.

from functools import cache
import math

def expected_draws(probabilities):
    ps = tuple(probabilities)
    if not ps or any(not math.isfinite(x) or x < 0 for x in ps):
        raise ValueError("finite nonnegative probabilities required")
    if not math.isclose(sum(ps), 1.0, rel_tol=0, abs_tol=1e-12):
        raise ValueError("probabilities must sum to one")
    if any(x == 0 for x in ps):
        return math.inf
    full = (1 << len(ps)) - 1
    @cache
    def remaining(mask):
        if mask == full:
            return 0.0
        missing = [i for i in range(len(ps)) if not mask & (1 << i)]
        mass = sum(ps[i] for i in missing)
        future = sum(ps[i] * remaining(mask | (1 << i)) for i in missing)
        return (1.0 + future) / mass
    return remaining(0)

The function requires a nonempty probability vector, although the mathematical empty-target case has completion time zero. The exact published function was executed locally. It returns 14.7 for six equal probabilities and 6.654762 for (0.5,0.3,0.2). It rejects invalid probability vectors and returns infinity when a required type has zero probability. The mathematical recurrence is exact; floating-point evaluation has rounding error.

There are up to 2**n sets and up to n outgoing missing-type checks per state, giving an O(n*2**n) baseline. Do not market this exponential exercise as a scalable production collector estimator. Extremely small probabilities, large n, recursion depth and numerical stability require additional methods.

Does a mean of 100 draws imply completion by 100?

No. An expectation averages completion times over repeated experiments. A finite-budget success probability asks whether this particular experiment finishes by a specified count.

For our 99%/1% example and a positive integer budget B, failure to complete means every draw was A or every draw was B. Those events are disjoint, so P(T <= B) = 1 - 0.99**B - 0.01**B.

At 100 draws, completion probability is approximately 63.3968%, despite the mean being approximately 100.01. About 36.6% of independent collections remain unfinished at that deadline. Neither “the average is100” nor “we usually see the common type quickly” establishes95% coverage.

If the interviewer requests a 95% success budget for this specific example, solve the probability inequality rather than round the mean. At 299 draws the completion probability first exceeds 95%. This is a distribution-specific result, not a universal multiplier for coupon collection.

Our preparation recommendation is to keep a small answer ledger: the stopping variable, the requested quantity, and the model. Mean completion time, deadline success and expected capped runtime belong on different lines. This separation also makes the next simulation's failure mode easy to recognize.

Simulate the experiment without hiding capped failures

The official Python random documentation describes weighted sampling with replacement and separate Random instances. Our original simulation receives a valid nonempty probability vector and positive integer trial count and cap. It uses an explicit seed and reports both completed draw counts and the runtime of every capped experiment.

import random

def simulate(ps, trials, cap, seed):
    rng = random.Random(seed)
    completed, capped = [], []
    for _ in range(trials):
        seen = set()
        for draws in range(1, cap + 1):
            seen.add(rng.choices(range(len(ps)), weights=ps, k=1)[0])
            if len(seen) == len(ps):
                completed.append(draws)
                break
        capped.append(draws)
    return completed, capped

In 20,000 six-type runs with seed 20261004 and a 1,000 draw cap, the completed mean was 14.6929 and no run was censored. That agrees closely with 14.7 for this fixture; it is empirical consistency, not a proof of the expectation.

Using the same seed, 20,000 runs of the 99%/1% experiment with a100 draw cap produced 12675 completed collections and 7325 unfinished collections. The completed-only mean was 42.1446, while the mean runtime across every capped run was 63.3342.

Neither number estimates the untruncated 100.010101 mean directly. Completed-only averaging selects experiments that finished quickly enough. Averaging all capped runtimes estimates E[min(T,100)], a different quantity. Keeping the censored count exposes the reason those averages are smaller.

Our testing recommendation is to record probabilities, seed, runtime version, trial count and cap. A seed alone does not establish identical results across every algorithm or environment. If a cap is necessary, name the censored observations and avoid quietly dropping them from the reported experiment.

What changes when the stopping rule becomes a decision?

“Stop when all types appear” defines a hitting time. “Stop after100 draws” defines a budget. “After each draw, decide whether another sample is worth its cost” defines a decision problem with a reward and information state. They cannot share an answer merely because all involve repeated draws.

For an adaptive policy, state what the collector knows, the cost of another draw, the value of completion, and whether probabilities can be changed. A reward for any new type differs from a reward paid only for the full set. A policy that can choose which type to purchase has changed the sampling mechanism.

If probabilities are unknown, ten repeated labels do not prove that other labels have zero probability. Any coverage claim needs assumptions or evidence about unseen mass. Our inference for interview preparation is to explain that identifiability boundary before proposing a confident stopping threshold.

Practise the changed assumption, not only the memorized sum

These verified questions cover collector reasoning, random-process expectations, replacement assumptions and decision rules. They are practice records, not a fixed probability-screen sequence.

Question	Useful collector follow-up
Solve probability and expectation problems	Derive the fair-die stages, then replace one face probability
Compute probabilities and expectations in random processes	Define a waiting variable and its conditioning state
Compute urn-draw probabilities and expectations	Explain why without-replacement sampling changes the model
Calculate Expected Impressions and Probability for Users	Distinguish a fixed draw budget from a completion-time question
Compute optimal stopping in a die-rolling game	Add costs and rewards before calling a rule optimal

Rehearse the uniform stages, the two-type unequal-odds counterexample, and the capped-simulation diagnosis. Each answer should identify exactly what is random and exactly when observation stops.

Sources and Further Reading

• MIT: coupon collector tutorial transcript
• Random Services: classical coupon collection
• Boneh and Hofri: The Coupon-Collector Problem Revisited
• Python: weighted pseudo-random sampling

References checked October 4, 2026. Exact-state and seeded simulation fixtures were executed offline; no interview outcome or real-world coverage guarantee is claimed.