Misra-Gries Heavy Hitters Algorithm

Reported in interviews at Jane Street

Problem statement

You are processing a stream of $n$ items, where each item is one of many possible keys. A key is called a heavy hitter if it appears more than $n/k$ times in the stream.

Design a single-pass streaming algorithm (Misra-Gries) that uses only $k - 1$ counters and returns a set of candidate keys such that:

  • Every true heavy hitter is in the candidate set (no false negatives).
  • The candidate set contains at most $k - 1$ keys (so there may be false positives).

Implement the function:

def misra_gries(stream, k):
    ...

Apply the Misra-Gries counter rule in one pass:

  • if x already has a counter, increment it;
  • else if fewer than k - 1 counters are in use, give x a counter set to 1;
  • else decrement every counter by 1 and drop any that reach 0 (do not insert x).

Return the surviving candidate keys as a list sorted in ascending order.

Target: $O(n)$ time, $O(k)$ space.

Example

misra_gries([1, 2, 3, 4, 5], 3) -> [4, 5]

With k = 3 there are only k - 1 = 2 counters. Every element is distinct, so the two slots fill with 1 and 2 and only 3 triggers a decrement; 4 and 5 then take the freed slots. Tracing: slots fill with 1 and 2; seeing 3 (a new key, no free slot) decrements both to 0 and empties the dict; then 4 and 5 refill the two now-free slots, so both survive and are returned sorted as [4, 5].

Show hint

If an item with no free slot could cancel against one occurrence of every tracked key, how much damage could such cancellations do to a truly frequent key?

Relevant roles: ML Engineer, Data Scientist, MLOps Engineer and Applied Scientist.

Related free problems