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, incrementtable[i][h_i(word) mod w]. - Estimate(word): take the minimum of those
dcounters.
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
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, an AI coding interview assistant.