# Coding Interview: Top K Frequent Words with a Count-Min Sketch (Streaming Variant) A common follow-up to "top K frequent words" is: *what if the stream is too large to keep an exact count for every word?* The answer interviewers look for is an approximate counter plus a small heap. ## Exact version first For a list that fits in memory: count with a hash map, then keep a min-heap of size K keyed by (count, word). O(n log K) time, O(n) space. Say this first so the interviewer knows you have the baseline. ## Count-Min Sketch A count-min sketch is a 2D array of counters with `d` rows and `w` columns and `d` independent hash functions. - **Add(word)**: for each row `i`, increment `table[i][h_i(word) mod w]`. - **Estimate(word)**: take the minimum of those `d` counters. Collisions only ever add to a counter, so the estimate never undercounts; it overcounts by at most `eps * N` with probability `1 - delta` when `w = ceil(e / eps)` and `d = ceil(ln(1 / delta))`. For eps = 0.001 and delta = 0.01 that's about 2,719 x 5 counters, a few dozen KB, regardless of how many distinct words there are. ## Putting it together ```python import heapq, hashlib class CMS: def __init__(self, w=2719, d=5): self.w, self.d = w, d self.t = [[0] * w for _ in range(d)] def _h(self, x, i): h = int(hashlib.blake2b(f"{i}:{x}".encode(), digest_size=8).hexdigest(), 16) return divmod(h, self.w)[1] def add(self, x): for i in range(self.d): self.t[i][self._h(x, i)] += 1 def est(self, x): return min(self.t[i][self._h(x, i)] for i in range(self.d)) def stream_top_k(stream, k): cms, heap, inheap = CMS(), [], {} for word in stream: cms.add(word) c = cms.est(word) if word in inheap: inheap[word] = c # lazily refreshed; rebuild heap at the end elif len(heap) < k: heapq.heappush(heap, (c, word)); inheap[word] = c elif c > heap[0][0]: _, old = heapq.heapreplace(heap, (c, word)) inheap.pop(old, None); inheap[word] = c return sorted(inheap.items(), key=lambda p: -p[1]) ``` ## What to discuss - The result is approximate; heavy hitters are reliable, ties near the cutoff are not. - Counters can be merged across machines by adding tables cell by cell, which makes it a good fit for distributed log processing. - Alternatives: Misra-Gries / Space-Saving give deterministic guarantees for heavy hitters with O(K) memory. --- *Disclosure: I work on [Linkjob AI](https://www.linkjob.ai/), an AI coding interview assistant.*