| @@ -0,0 +1,58 @@ | |||
| 1 | + | # Coding Interview: Top K Frequent Words with a Count-Min Sketch (Streaming Variant) | |
| 2 | + | ||
| 3 | + | 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. | |
| 4 | + | ||
| 5 | + | ## Exact version first | |
| 6 | + | ||
| 7 | + | 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. | |
| 8 | + | ||
| 9 | + | ## Count-Min Sketch | |
| 10 | + | ||
| 11 | + | A count-min sketch is a 2D array of counters with `d` rows and `w` columns and `d` independent hash functions. | |
| 12 | + | ||
| 13 | + | - **Add(word)**: for each row `i`, increment `table[i][h_i(word) mod w]`. | |
| 14 | + | - **Estimate(word)**: take the minimum of those `d` counters. | |
| 15 | + | ||
| 16 | + | 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. | |
| 17 | + | ||
| 18 | + | ## Putting it together | |
| 19 | + | ||
| 20 | + | ```python | |
| 21 | + | import heapq, hashlib | |
| 22 | + | ||
| 23 | + | class CMS: | |
| 24 | + | def __init__(self, w=2719, d=5): | |
| 25 | + | self.w, self.d = w, d | |
| 26 | + | self.t = [[0] * w for _ in range(d)] | |
| 27 | + | def _h(self, x, i): | |
| 28 | + | h = int(hashlib.blake2b(f"{i}:{x}".encode(), digest_size=8).hexdigest(), 16) | |
| 29 | + | return divmod(h, self.w)[1] | |
| 30 | + | def add(self, x): | |
| 31 | + | for i in range(self.d): | |
| 32 | + | self.t[i][self._h(x, i)] += 1 | |
| 33 | + | def est(self, x): | |
| 34 | + | return min(self.t[i][self._h(x, i)] for i in range(self.d)) | |
| 35 | + | ||
| 36 | + | def stream_top_k(stream, k): | |
| 37 | + | cms, heap, inheap = CMS(), [], {} | |
| 38 | + | for word in stream: | |
| 39 | + | cms.add(word) | |
| 40 | + | c = cms.est(word) | |
| 41 | + | if word in inheap: | |
| 42 | + | inheap[word] = c # lazily refreshed; rebuild heap at the end | |
| 43 | + | elif len(heap) < k: | |
| 44 | + | heapq.heappush(heap, (c, word)); inheap[word] = c | |
| 45 | + | elif c > heap[0][0]: | |
| 46 | + | _, old = heapq.heapreplace(heap, (c, word)) | |
| 47 | + | inheap.pop(old, None); inheap[word] = c | |
| 48 | + | return sorted(inheap.items(), key=lambda p: -p[1]) | |
| 49 | + | ``` | |
| 50 | + | ||
| 51 | + | ## What to discuss | |
| 52 | + | ||
| 53 | + | - The result is approximate; heavy hitters are reliable, ties near the cutoff are not. | |
| 54 | + | - Counters can be merged across machines by adding tables cell by cell, which makes it a good fit for distributed log processing. | |
| 55 | + | - Alternatives: Misra-Gries / Space-Saving give deterministic guarantees for heavy hitters with O(K) memory. | |
| 56 | + | ||
| 57 | + | --- | |
| 58 | + | *Disclosure: I work on [Linkjob AI](https://www.linkjob.ai/), an AI coding interview assistant.* | |
linkjobai / Coding Interview: Top K Frequent Words with a Count-Min Sketch (Streaming Variant)
Last active 5 days ago
Interview prep notes
linkjobai revised this gist 5 days ago · 2b8b6a0
1 file changed, 58 insertions