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.