Interview prep notes

linkjobai revised this gist 5 days ago · 2b8b6a0

1 file changed, 58 insertions

bloomcount.md (file created)
@@ -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.*