Interview prep notes

Revision 2b8b6a0d026267aa3299a5fc9ab57caaf7ab8532

bloomcount.md Raw

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

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.