Coupon collector partial vs complete

This question centers on the classic coupon collector scenario, framed in two complementary ways. The first part asks about the average number of trials needed to obtain a complete set of distinct items when each trial yields one random item from a fixed catalog. The second part turns the perspective around: given a fixed number of trials already made, it asks for the expected number of distinct item types seen so far. Together, they probe a candidate's understanding of how expected values behave in processes with repeated sampling and increasing difficulty of collecting new outcomes.

Solving both parts leans heavily on linearity of expectation and the use of indicator random variables to track whether each type has appeared. The interviewer is watching for a clean decomposition of the problem into per-type events, correct handling of dependence without trying to compute complicated joint distributions, and the ability to identify and manipulate series that naturally arise in such settings. Clear probabilistic reasoning, comfort moving between "time to completion" and "coverage after fixed time," and the ability to generalize the method beyond the toy story are central to a strong answer.

What it tests

This problem class is governed by the linearity of expectation and the use of indicator variables to count occurrences of rare or distinct events. The key insight is that, even when events are dependent (such as collecting distinct types), the expected value of the sum is the sum of the expected values, allowing us to decompose the problem into manageable parts. For the coupon collector, each new type is harder to obtain because the pool of 'new' types shrinks, leading to a harmonic sum structure. For counting distinct types in repeated sampling, the probability that a given type is missing after several draws is independent of the presence or absence of other types, so the expected count can be found by summing over all types. This approach generalizes to any scenario where you are collecting or observing rare events across repeated trials, not just coupons.