Count-Min Sketch
maang.io System Design Series
A count-min sketch is a small 2D array of counters and a few hash functions that estimates how many times you've seen an item β using far less memory than a real hash map. It may overestimate (from collisions) but never underestimates, which makes it perfect for frequency counting and "heavy hitters" (top-K) over streams too big to store exactly.
This deep dive comes in three parts:
- Foundations & Core Concepts β the counter grid, the MIN trick, and the accuracy-vs-space bargain.
- Internals β the error bounds
Ξ΅/Ξ΄, sizing the width and depth, and contrasts with Bloom filters and HyperLogLog, with worked numbers. - Interview β Staff/Principal Q&A: when approximate counting wins, sizing, and streaming trade-offs.
Count-Min Sketch β Part 3: System Design & Interview Mastery
maang.io System Design Series
What is this?
You now know the Count-Min Sketch from the three-bouncer intuition down to the Ξ΅/Ξ΄ math. This chapter is where that pays off. An interviewer rarely asks "what is a Count-Min Sketch?" cold β instead they hand you a system-design prompt where an exact counter would blow the memory budget, and they watch whether you reach for the sketch at the right moment, size it out loud, and defend its noisy-tail weakness when they push. That instinct is the senior signal.
We'll do two things: see where the sketch fits in real designs (with diagrams), then run a mock interview β for each question, what they're really asking, a model answer, and the senior line that says you've shipped this for real.
The one-line idea: interviewers use Count-Min Sketch to test whether you can spot the "approximate frequency over a firehose" shape, pick the right member of the sketch family (not Bloom, not HyperLogLog, not an exact map), do the memory-vs-accuracy math, and stay honest about the one thing it's bad at β the long tail.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson