Top K Frequent Numbers from a Continuous Stream

Problem Statement

Design a data structure that supports a continuous stream of numbers with the following operations:

1. add(num) — Add a number to the stream
2. topK(k) — Return the current top K most frequent numbers

Operations can come in any order and should work efficiently for an infinite stream.

Constraints

• 1 <= num <= 10^5
• 1 <= k <= number of distinct elements seen so far
• Stream can be infinite — memory should be bounded reasonably
• add should be O(1) or O(log n)
• topK should be efficient (better than sorting all elements each time)

Example

add(1)
add(2)
add(1)
add(3)
add(2)
add(1)

topK(2) → [1, 2]   // 1 appears 3 times, 2 appears 2 times

add(4)
add(4)
add(4)
add(4)

topK(1) → [4]      // 4 now appears 4 times, most frequent
topK(3) → [4, 1, 2]

What the Interviewer Expects

1. HashMap for frequency counting — {num → count}. O(1) per add.
2. Min-heap of size K for topK — maintain a heap of the K most frequent. If a new element's frequency exceeds the heap minimum, swap it in.
3. Alternative: Bucket sort — buckets indexed by frequency. topK iterates from highest bucket down. Better for frequent topK calls.
4. Trade-off discussion: Heap gives O(n log k) for topK. Bucket sort gives O(n) worst case for topK but O(1) amortized for add.
5. Streaming consideration: Can't store all raw numbers — only need frequency map + top-k structure.

Follow-ups

1. What if you need topK in O(1) time? Is that achievable? (hint: maintain a sorted structure or use bucket + doubly linked list like LFU cache)
2. What if elements can be removed from the stream? How does your design change?
3. What if k changes between queries? How do you handle different k values efficiently?
4. What if you need approximate topK for a massive stream that doesn't fit in memory? (hint: Count-Min Sketch)