Last active 5 days ago
interview
Interview prep notes
0
0
1
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.