A strong answer
The exact approach is a hash set of user IDs per service per day, shipped wherever the report is assembled. Both of its costs grow with the audience — memory on every service and bandwidth at aggregation — and the report only needs a number. Replace each set with a HyperLogLog: 16,384 registers at p = 14, about 12 KB in its dense form, and one hash per event that updates a single register with a maximum. Memory is fixed the day you choose p, no matter how many users arrive, and no ID ever leaves the service that observed it.
Aggregation becomes a per-register maximum: fold every service's sketch into a running union in one pass over the registers, then estimate once. Users seen by several services are counted once, because they wrote the same ranks to the same registers in every copy — this is why merging by maximum works and merging by addition does not. Daily sketches are 12 KB each, so a year of them is a rounding error, and any window — weekly, monthly, all-time — is a merge of the relevant days.
The number you report carries an error you must state: the standard error of a p = 14 sketch is 1.04 / sqrt(16384) = 0.81%, roughly one standard deviation, so about a third of estimates fall outside it. If the business needs 0.4%, use p = 16 for 48 KB; if 1.6% is fine, p = 12 costs 3 KB. Exactness is not on offer: the sketch cannot list the users, cannot remove one user's contribution, and cannot be corrected after the fact — if the count feeds a bill, keep the raw IDs somewhere too.
What the interviewer is listening for
- Fixed state chosen up front: m registers, one hash per event, a max update — memory independent of cardinality.
- Union as register-wise maximum, which is what makes fan-out and re-merge work without shipping IDs.
- The error as a formula,
1.04 / sqrt(m), quoted as a standard error rather than a bound, and sized from a stated target. - Clear naming of what the sketch cannot do: no members, no deletion, no correction.
Common mistakes
- Adding per-service estimates (double-counts shared users) or averaging them (quietly wrong when overlap varies).
- Quoting "within 0.8%" as a guarantee instead of one standard error, or forgetting to quote any error at all.
- Choosing p by memory alone without tying it to the accuracy the decision needs.
- Keeping an ID store around for contingencies — the growth problem returns — or claiming the sketch anonymizes users: it retains no IDs, but frequency patterns in the registers can still leak information.