Top K / Heavy Hitters Problem

Phase 1 — Clarify & Scope

Interviewer: Design a system that finds the top K most frequently occurring items in a data stream — think "top 10 trending hashtags on Twitter" or "top 100 most-searched queries on Google." What do you want to clarify?

Candidate: A few questions:

1. What's the data volume — events per second?
2. What's K? Top-10, top-100, or top-1000?
3. How large is the item space — how many unique items (hashtags, queries)?
4. What freshness is required — last 1 minute, last 1 hour, last 24 hours?
5. Exactness — can we tolerate approximate results, or does every item need an exact count?

Interviewer: Twitter-scale trending: 100,000 tweets/sec, each tweet has up to 5 hashtags → ~500,000 hashtag events/sec. Find top-100 trending hashtags. Item space: 100 million unique hashtags. Freshness: last 1 hour, updated every 1 minute. Approximate results are acceptable (within 0.1% error).

Candidate: Let me size the problem:

$\text{Event rate} = 500{,}000 \text{ hashtag events/sec}$

$\text{Events per hour} = 500{,}000 \times 3{,}600 = 1.8 \text{ billion events/hour}$

With exact counting (HashMap: hashtag → count): $\text{Memory} = 100\text{M unique hashtags} \times (32 \text{ bytes avg hashtag} + 8 \text{ bytes count}) = 4 \text{ GB}$

With Count-Min Sketch (ε=0.001, δ=0.001): $\text{Width} = \lceil e/\varepsilon \rceil = 2{,}719 \text{ counters}$ $\text{Depth} = \lceil \ln(1/\delta) \rceil = 7 \text{ hash functions}$ $\text{Memory} = 2{,}719 \times 7 \times 4 \text{ bytes} = 76 \text{ KB}$

That's a ~53,000×…