How do you implement a Count-Min Sketch for streaming frequency estimates?

1. Prompt

A logging platform receives event keys such as URLs or product IDs, potentially billions of events. Implement add(key) and estimate(key) with fixed memory. Return an approximate occurrence count and discuss error, shard merges, counter overflow, and when an exact structure is required.

2. Constraints and clarifications

• Each event is seen once; all keys cannot fit in a hash table.
• Overestimation is acceptable, with parameters controlling the error probability.
• Start with non-negative updates; deletion, negative weights, and time-based expiry need extra constraints.
• Shards can be merged directly only when width, depth, hash seeds, and counter encoding match.

3. Core approach

Count-Min Sketch (CMS) keeps d rows of w non-negative counters. Each row has an independent hash function that maps a key to one column. An update increments every selected counter; a query returns the minimum selected counter. The true count appears in every selected row, while collisions from other keys can only add to counters, so the minimum is an upper bound that does not undercount.

Using error epsilon and failure probability delta, common choices are w = ceil(e / epsilon) and d = ceil(ln(1 / delta)). With total update weight N, the estimate is at most the true count plus epsilon * N with probability at least 1 - delta. This is a probabilistic error bound, not an absolute guarantee for every query.

4. Reference implementation

init(epsilon, delta):
  w = ceil(e / epsilon)
  d = ceil(ln(1 / delta))
  table = array(d, w, fill=0)
  seeds = choose_d_independent_seeds()

add(key, weight=1):
  require weight >= 0
  for row in 0..d-1:
    col = hash(key, seeds[row]) mod w
    table[row][col] += weight
  total += weight

estimate(key):
  values = []
  for row in 0..d-1:
    col = hash(key, seeds[row]) mod w
    values.append(table[row][col])
  return min(values)

merge(other):
  require same w, d, seeds, counter encoding
  for each cell (r, c):
    table[r][c] += other.table[r][c]
  total += other.total

5. Complexity and correctness

Each update and query touches d cells, so time is O(d). Space is O(d * w), independent of the number of distinct keys. With non-negative updates, the minimum remains at least the true frequency. Increasing width reduces collision bias; increasing depth lowers the probability of exceeding the error bound, while both increase memory and hash work linearly.

Counters need sufficient integer width or an explicit saturation policy; unsigned wraparound would invalidate the no-undercount property. A shard merge adds corresponding cells, and all hash mappings must match. Combining different layouts produces an uninterpretable result.

6. Follow-ups and traps

• CMS answers the approximate count of a known key; it does not enumerate Top-K. Keep a candidate set or use a heavy-hitter structure for that.
• Collisions only overestimate, so the estimate cannot recover an exact frequency or exact distinct set.
• Negative updates break monotonicity and the simple proof; deletion and sliding windows usually require time buckets or a decaying structure.
• A time window cannot be maintained by subtracting old totals unless rollback-capable bucket state is retained.

7. Further reading

Compare CMS with an exact hash map, Bloom filter, HyperLogLog, and Frequent Items Sketch: they target frequency queries, membership, cardinality, and heavy-hitter identification respectively. Choose based on the query, error budget, deletion needs, and whether candidate keys must be emitted.

8. Interview scoring points

Can explain the counter matrix

The candidate should describe independent row hashes, updating every row, taking the minimum, and why collisions can only raise a counter.

Can state the error parameters

They should connect epsilon, delta, w, d, and total weight N, distinguishing a probability bound from an absolute exact guarantee.

Can handle engineering boundaries

They should cover counter overflow, shard-parameter compatibility, cell-wise addition, and extra design for negative weights or sliding windows.

Can choose a matching structure

They should recognize that CMS does not provide Top-K, exact membership lists, or exact cardinality, and switch to an exact map, HLL, or heavy-hitter structure when requirements change.