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. ```hint Where does the heap live Decide whether the heap is built when a query arrives or kept up to date on every `add`, and compare what each choice costs per operation. ``` #### 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. ```hint How far can one add move an element A single `add` raises exactly one count by exactly one. Think about what that means for where the element sits relative to elements with other counts. ``` #### 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 ### What a Strong Answer Covers - Honest per-operation costs for both designs, not only asymptotic labels - The invariants of the O(1) structure and why the query does not degrade - Correct handling of ties, of `k` larger than the number of distinct elements, and of new elements - Memory cost, and how the design changes when exact counting no longer fits ### Follow-up Questions - Counts should cover only the last hour of events. What must change, and can updates stay O(1)? - The number of distinct elements is far larger than memory. How do you report an approximate top K, and what error guarantee can you give? - The stream is split across many machines. How do you compute an exact global top K, and when is merging each machine's local top K wrong? - If "top K" meant the K largest values seen so far rather than the most frequent, how would the design change?