What is a Count-Min Sketch and How Does It Estimate Frequencies?

Learn what a Count-Min Sketch is, how it estimates item frequencies in streams, and why its error is one-sided.

hardQ113 of 224 in System Design Est. time: 6 minsLast updated: July 2026

Expected Interview Answer

A Count-Min Sketch is a probabilistic data structure that estimates how many times each item has appeared in a stream using a small, fixed amount of memory, at the cost of occasionally overestimating (never underestimating) the true count.

It is implemented as a 2D array of counters with d rows, each paired with an independent hash function, and w columns. To record an occurrence of an item, it is hashed by each of the d hash functions and the counter at the resulting column in each row is incremented. To estimate an item’s count, the same d hash functions are computed and the minimum value across the d corresponding counters is returned, since taking the minimum cancels out most of the effect of hash collisions from other items landing in the same cell. Because different items can collide into the same counter, the estimate is always greater than or equal to the true count, never less — this one-sided error is what makes the structure usable for approximate top-K and frequency analysis at massive scale, as used in Twitter’s and Redis’s stream analytics.

Uses sublinear memory regardless of how many distinct items pass through the stream
Gives frequency estimates with a guaranteed one-sided error (only overestimates, never underestimates)
Supports constant-time O(d) updates and queries independent of stream size
Enables approximate heavy-hitter / top-K detection over unbounded streams in real time

AI Mentor Explanation

A Count-Min Sketch is like several independent scorers each keeping a compact tally grid of how often each shot type occurs, using shorthand codes that occasionally collide between two different shot types. To estimate how often a “cover drive” happened, you check each scorer’s tally at that shot’s code and take the smallest number reported, since a low count from any one scorer means less collision noise affected it. The estimate can only be too high, never too low, because a collision can only add extra counts, not remove real ones. That compact, minimum-of-many-estimates approach is exactly how a Count-Min Sketch tracks approximate frequencies.

Step-by-Step Explanation

Step 1
Allocate the 2D counter grid
Create a d-by-w array of counters initialized to zero, with d independent hash functions, one per row.
Step 2
Update on each occurrence
For each item seen in the stream, hash it with all d functions and increment the counter at each resulting (row, column) position.
Step 3
Query an item’s estimated count
Hash the item with the same d functions and read the counter at each resulting position across all rows.
Step 4
Take the minimum
Return the smallest of the d counter values as the frequency estimate, since it is least affected by hash collisions from other items.

What Interviewer Expects

Explains the d-by-w counter grid and multiple hash functions accurately
States that estimates are always greater than or equal to the true count (one-sided error)
Explains why taking the minimum across rows reduces the impact of collisions
Names a real use case: stream analytics, approximate top-K / heavy hitters, network traffic monitoring

Common Mistakes

Confusing Count-Min Sketch with a Bloom filter (Bloom filters answer membership, not frequency)
Claiming the estimate can be an undercount (it cannot, by construction)
Forgetting that increasing width (w) and depth (d) reduces error but costs more memory
Not mentioning that it is built for unbounded/streaming data where storing exact counts is infeasible

Best Answer (HR Friendly)

“A Count-Min Sketch is a compact structure that gives you an approximate answer to “how many times has this happened” without storing an exact counter for every possible item. It might occasionally tell you a count is a bit higher than reality, but it will never tell you it is lower, which makes it useful for tracking trends in huge, fast-moving streams of data cheaply.”

Code Example

Simplified Count-Min Sketch implementation

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 _positions(self, item):
        for row in range(self.depth):
            h = hashlib.sha256(f"{row}:{item}".encode()).hexdigest()
            yield row, int(h, 16) % self.width

    def add(self, item, count=1):
        for row, col in self._positions(item):
            self.table[row][col] += count

    def estimate(self, item):
        # minimum across rows cancels most collision noise
        return min(self.table[row][col] for row, col in self._positions(item))

cms = CountMinSketch()
for event in stream_of_page_views():
    cms.add(event.page_id)

approx_views = cms.estimate("page_123")  # always >= true count

Follow-up Questions

Why does taking the minimum across rows reduce the estimation error compared to using a single hash function?
How does a Count-Min Sketch differ from a Bloom filter in what problem it solves?
How would you use a Count-Min Sketch to build an approximate top-K "heavy hitters" list?
How do width (w) and depth (d) affect the accuracy and confidence of the frequency estimate?

MCQ Practice

1. What kind of error can a Count-Min Sketch produce?

2. Why does a Count-Min Sketch take the minimum across its d rows when estimating a count?

3. What is the main practical use case for a Count-Min Sketch?

Flash Cards

1 / 4

What is a Count-Min Sketch and How Does It Estimate Frequencies?

Expected Interview Answer

AI Mentor Explanation

Step-by-Step Explanation

Allocate the 2D counter grid

Update on each occurrence

Query an item’s estimated count

Take the minimum