How would you size the seen-set for deduplicating a billion-row clickstream, and what changes when it exceeds RAM?

## Step one: convert the structure into bytes The defining senior move here is refusing to reason in asymptotics. "O(n) auxiliary space" is true and useless; the job either fits on the machine or it does not, and only arithmetic decides that. Take a billion rows keyed by a 16-byte identifier, worst case all distinct: | Component | Estimate | | --- | --- | | Raw key bytes | 10⁹ × 16 B = 16 GB | | Per-entry bookkeeping (link/metadata/alignment) | commonly 8–32 B per entry | | Slack from load factor (empty slots kept for fast probes) | typically 30–50% more slots than entries | | **Realistic total** | **roughly 40–60 GB** | The two multipliers people forget are the last two. A keyed lookup structure is fast precisely because it is not full: it keeps spare slots so that finding a key takes a short, bounded search, and it grows itself before it fills up. That headroom is not waste to be optimized away — it is what buys the expected-constant lookup — but it means the memory number is a multiple of the key bytes, never equal to them. A candidate who answers "16 GB, so it fits in a 32 GB box" has made the classic error and will discover it in production. The same census applies to the neighbouring tools, and it is worth having the numbers ready: a per-element visited marker over the same data is one bit or one byte per element only if elements are densely indexed; a frequency map is bounded by distinct keys, not rows; a two-dimensional table over two sequences of length n and m is n·m entries, which crosses gigabytes at surprisingly modest n. ## Step two: when it does not fit ### Partition by key hash Send every row to one of k buckets by hashing its key. Identical keys hash identically, so every duplicate pair lands in the same bucket — which means each bucket can be deduplicated completely independently, and the peak memory is the largest bucket's distinct-key count rather than the whole stream's. With k chosen so that each bucket's set comfortably fits, a job that could not run at all becomes k jobs that can, either sequentially on one machine or spread across several. The price is an extra full read and write of the data to form the buckets, plus sensitivity to skew: if one key or one hash range dominates, that bucket is still too big and you either subdivide it or handle the hot keys specially. ### Bring duplicates adjacent by ordering If the rows are ordered by key, duplicates are neighbours, and a single sequential scan holding exactly one previous key emits the distinct rows — working memory drops to a buffer plus one key, independent of how many distinct keys exist. The memory problem is genuinely solved; the cost has moved into ordering data that does not fit in memory, which is paid in reads and writes rather than resident bytes. That is the trade to state explicitly in the interview: the set-based approach is one pass and lots of memory, the ordered approach is bounded memory and more I/O. (The accounting of how many passes the ordering itself takes is its own subject — say that it is the dominant cost and move on.) ### Trade exactness for bits A compact probabilistic membership filter stores a few bits per element instead of the whole key, cutting a tens-of-gigabytes structure to about a gigabyte. It never reports a false negative — anything it says is new really is new — but it may report a false positive, wrongly claiming an unseen key was already seen. That asymmetry decides whether it is usable: if dropping a genuinely-new row occasionally is acceptable (traffic estimation, sampling), the filter alone is enough; if it is not, use the filter as a cheap pre-check and confirm the small set of positives against an exact structure or a durable store. ### Question the requirement The cheapest fix is often to shrink what has to be remembered. Deduplication is frequently only meaningful within a window — the same click reported twice within a minute — in which case the set holds a minute of keys, not a billion. Or the key can be narrowed: storing a 64-bit digest instead of a full identifier halves the key bytes at a small, quantifiable collision risk. Always ask what exact guarantee the business actually needs before engineering for the strictest reading. ## What a strong answer sounds like "Distinct keys times bytes per entry, and bytes per entry is the key plus overhead plus load-factor slack — call it three times the raw key size, so tens of gigabytes for a billion 16-byte keys. That does not fit, so I would hash-partition into buckets small enough to dedupe independently, which costs one extra pass. If the window is bounded I would exploit that first, and if approximate dedup is acceptable a bit-per-element filter is an order of magnitude cheaper." The shape of that answer — arithmetic, then a named alternative, then the price of the alternative — is what distinguishes an engineer who has run out of memory in production from one who has only read about it.