Track Top-K Frequent Elements from an Unbounded Stream

# Track Top-K Frequent Elements from an Unbounded Stream Design a component that consumes an unbounded stream of elements and answers top-`k` frequency queries while ingestion continues. Explain how the design changes when results must be exact versus approximate and when the query covers all history versus a recent time window. ### Constraints & Assumptions - The stream has no final element, so results are snapshots defined at query time. - The number of distinct elements may exceed one machine's memory. - Events may be duplicated or replayed unless the ingestion contract supplies a stable event ID. - Exact latency, throughput, `k`, cardinality, error tolerance, and window semantics should be clarified. ### Clarifying Questions to Ask - Must counts and rankings be exact, or is a bounded approximation acceptable? - Is the scope all-time, a fixed window, a sliding window, or several windows? - How often are queries issued, and how stale may a result be? - Are ties ordered by value, first occurrence, or another stable rule? - Can events be replayed, corrected, or arrive out of order? ### What a Strong Answer Covers - A precise snapshot, tie, replay, and window contract before choosing a data structure. - Exact single-node counting with a frequency map and a structure that updates top candidates without sorting all keys per query. - The unbounded-cardinality memory limitation and an approximate heavy-hitter method with an explicit error guarantee. - Partitioned ingestion, local summaries, merge behavior, skew, hot keys, and checkpoint recovery. - Window expiration or bucket rotation that removes old contribution correctly. - Idempotency or at-least-once implications, query consistency, observability, and tests using known distributions and adversarial updates. ### Follow-up Questions 1. Why is exact all-time top-k impossible with bounded memory when distinct elements are unbounded? 2. How would you merge per-partition heavy-hitter summaries without claiming an exact global ranking? 3. What state must expire when a sliding window advances? 4. A single element becomes extremely hot. How do you avoid one partition becoming the ingestion bottleneck? 5. Which result do you return when two elements tie at the `k` boundary?