20.6 How do you find the top K and heavy hitters?

At the door: The bouncer can't remember everyone, but keeps a short list of the five regulars seen most often. Each time someone comes in, they check the tally boards: if this person's count is now higher than the lowest regular's, they swap them onto the list.

In the system: Top-K (or heavy hitters) means finding the K most frequent items in a stream: trending searches, most-played songs, busiest API clients. Exact counting needs a counter for every distinct item; at scale, that's too much.

A common approach: count-min sketch + a small heap:

1. For each item, update the count-min sketch and read its estimated count.
2. Keep a min-heap of size K of the current leaders.
3. If the item is already in the heap, update its count. Otherwise, if its estimate beats the smallest in the heap, replace that one.

In the chapter's code, with a skewed stream of 100,000 searches, the top 5 from the sketch exactly match the true top 5.

Other ways to know by name:

• Misra-Gries and Space-Saving: keep K counters directly; when a new item arrives and all counters are taken, decrement or replace the smallest. Simple and accurate for truly frequent items.
• Exact counting with windows: for "trending in the last hour", count in a stream processor per time window, sharded by term, then merge the top lists (Chapter 35's leaderboard design).

Two details interviewers like:

• Trending isn't just most frequent. "the" or "harry potter" are always frequent. Trending means unusually frequent compared to normal: compare this hour's count with the usual for that term.
• Time windows: use a sketch per minute or hour and combine or decay them, so last week's hits fade.

Memory code: "Count roughly, keep the leaders, and swap out the weakest."

---