What is a Count-Min Sketch and When Would You Use One?
Learn how a count-min sketch estimates item frequency in massive streams with constant memory and one-sided error.
Expected Interview Answer
A count-min sketch is a probabilistic data structure that estimates the frequency of items in a massive stream using a fixed-size 2D array of counters and several hash functions, trading a small, one-directional error (it can only overestimate, never underestimate) for constant memory regardless of how many distinct items appear.
The sketch is a grid of w columns by d rows of counters; each of d independent hash functions maps an incoming item to one column in its own row, and incrementing that item's count bumps one counter in each of the d rows. To query an item's estimated frequency, you hash it the same d ways and take the minimum of the d counters — the minimum, rather than any single counter, cancels out most hash collisions from other items sharing a column. Because two different items can collide in a given row's column and inflate a counter, the estimate can only ever be too high, never too low, which is why it is called a one-sided error structure. Increasing width and depth shrinks the error bound and collision probability at the cost of more memory, letting engineers tune accuracy versus space explicitly, which is exactly why it powers heavy-hitter detection, network traffic analysis, and approximate query systems at massive scale where storing exact counts per item is infeasible.
- Constant memory regardless of the number of distinct items
- O(d) constant-time updates and queries
- Never underestimates a true frequency
- Tunable accuracy vs. memory tradeoff via width and depth
AI Mentor Explanation
A count-min sketch is like tracking how often each bowler concedes a boundary using a handful of small tally sheets instead of one row per bowler across the whole league. Each tally sheet uses a different rule to pick a column for a bowler's name, so the same bowler lands in a different column on each sheet, and one boundary bumps one column on every sheet. To estimate a bowler's boundary count, you check the smallest number across all their sheet columns, since a bigger number might just be inflated by a different bowler sharing that column. This never underestimates a bowler's true tally, but it can occasionally overestimate if unlucky collisions stack up, which is an acceptable tradeoff for tracking thousands of bowlers with only a few small sheets.
Step-by-Step Explanation
Step 1
Allocate a w x d counter grid
Pick width w and depth d based on desired error bound epsilon and confidence delta.
Step 2
Update: hash into each row
On each item occurrence, apply d independent hash functions to pick one column per row, incrementing all d counters.
Step 3
Query: take the minimum
Hash the item the same d ways and return the minimum of the d counters as the frequency estimate.
Step 4
Tune width/depth for accuracy
Larger w reduces per-row collision error; larger d reduces the probability that all rows collide badly, at the cost of more memory.
What Interviewer Expects
- Explain the w x d counter grid and d independent hash functions
- Explain why taking the minimum across rows cancels most collision error
- State the estimate is one-sided: it can only overestimate, never underestimate
- Name real use cases: heavy hitters, network traffic monitoring, approximate top-K, database query optimizers
Common Mistakes
- Confusing a count-min sketch with a Bloom filter (Bloom filters test membership, count-min estimates frequency)
- Forgetting the estimate is always ≥ true count, never below it
- Claiming it stores exact counts for small datasets — it is designed for streams too large to count exactly
- Not mentioning the width/depth tradeoff between accuracy and memory
Best Answer (HR Friendly)
“A count-min sketch is a compact way to estimate how often items appear in a huge stream without storing an exact counter for every single item. I would use it when I need to find heavy hitters or approximate frequencies at massive scale, accepting a small, always-upward error in exchange for constant memory.”
Code Example
import hashlib
class CountMinSketch:
def __init__(self, width=2000, depth=5):
self.width = width
self.depth = depth
self.table = [[0] * width for _ in range(depth)]
def _hash(self, item, row):
digest = hashlib.md5(f"{row}:{item}".encode()).hexdigest()
return int(digest, 16) % self.width
def add(self, item, count=1):
for row in range(self.depth):
col = self._hash(item, row)
self.table[row][col] += count
def estimate(self, item):
return min(
self.table[row][self._hash(item, row)]
for row in range(self.depth)
)Follow-up Questions
- How does a count-min sketch differ from a Bloom filter and a HyperLogLog?
- How would you use a count-min sketch to find the top-K most frequent items in a stream?
- How does increasing depth d improve the confidence bound on the error?
- How would you handle decaying old counts in a sliding-window frequency estimate?
MCQ Practice
1. What type of error can a count-min sketch's frequency estimate have?
Because hash collisions can only add extra weight to a counter, never remove it, the minimum-of-rows estimate can only be greater than or equal to the true count.
2. How does the query operation combine the d row estimates?
Taking the minimum across the d rows cancels out most of the inflation caused by hash collisions in any single row.
3. What is the main benefit of a count-min sketch over an exact hash-map counter?
A count-min sketch uses a fixed-size w by d grid no matter how many distinct items appear, unlike an exact counter map which grows with cardinality.
Flash Cards
What structure underlies a count-min sketch? — A w (width) by d (depth) grid of counters updated by d independent hash functions.
How do you query an item's estimated frequency? — Hash it d ways and take the minimum of the corresponding counters.
Can a count-min sketch underestimate a true frequency? — No — it is a one-sided error structure that can only overestimate.
Name a real use case for a count-min sketch. — Detecting heavy hitters in network traffic or approximate top-K frequency queries at scale.