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.