Streaming Top-K Frequent Elements with O(1) Updates Instead of a Heap

Elements arrive one at a time from an unbounded stream (for example, item IDs from an event log). Design a data structure that consumes the stream and can report, at any moment, the K elements that have appeared most often so far. Pseudocode is acceptable, but every operation's cost must be stated.

The structure supports two operations:

• add(x): record one more occurrence of element x.
• top_k(k): return up to k elements with the highest occurrence counts so far, most frequent first.

After you present a heap-based solution, the interviewer says they are not satisfied with it and pushes you to make processing each arriving element faster.

Constraints and Clarifications

• "Top K" here means by occurrence count, not by element value.
• Elements are hashable IDs, and one counter per distinct element fits in memory.
• Counts only grow: there are no deletions and no time window unless a follow-up introduces one.
• If fewer than k distinct elements have been seen, top_k(k) returns all of them.

Clarifying Questions

• How should elements with equal counts be ordered in the result?
• Is K fixed when the structure is created, or can every query ask for a different k?
• Roughly how many add calls arrive per top_k call? That decides whether the work should go on the write side or the read side.
• Must the answer be exact, or is an approximation acceptable if the number of distinct elements grows beyond memory?

Part 1 — A heap-based design

Design the structure with a hash map and a heap. Give the time cost of add and of top_k, and the memory cost, in terms of the number of distinct elements D and K.

What This Part Should Cover

• A correct heap-based design, including how an element already in the heap gets its count updated
• Per-operation time costs and memory
• Why the design is correct as counts change

Part 2 — Faster than a heap

The interviewer wants the per-element cost below what a heap gives. Design a structure where add(x) takes O(1) time and top_k(k) takes time proportional to k, and explain why each operation meets that bound.

What This Part Should Cover

• A data structure whose updates touch only a constant number of nodes
• The invariants that keep the structure correct, including what happens to groups that become empty
• A query that stops after k elements without scanning unrelated state
• A deterministic tie rule, and a small worked trace