Streaming Top-K Interview Questions: Exact Counts, Sketches, and Memory Budgets

Streaming Top-K interview questions are not solved by saying “use a heap.” The first decision is whether the answer must be exact, whether all distinct keys fit in memory, how often queries arrive, and what approximation guarantee the caller will accept. A heap can select candidates, but it does not replace the frequency state needed to know which items deserve selection.

Start with the candidate-reported Find top-K frequent elements in a stream. This guide develops the follow-ups that matter when the stream or key space is large: exact counts, query/update trade-offs, heavy-hitter summaries, Count-Min error bounds, candidate discovery, deletions, windows, and concrete memory arithmetic. PracHub records describe individual practice prompts; they do not establish a universal employer format.

Streaming Top-K Interview Questions: Quick Answer

If every distinct key fits in memory, keep an exact hash map key -> count. For infrequent queries, update in expected O(1) time and scan the U distinct keys with a size-k heap in O(U log k) per query. For frequent queries, add an indexed heap, ordered set, or frequency-bucket structure, while still keeping all U exact counts.

If U exceeds the memory budget, exact arbitrary Top-K is generally unavailable in one pass. State an approximation contract. Misra–Gries keeps a bounded candidate set and guarantees that sufficiently frequent items are not missed. Count-Min Sketch estimates a supplied key's count with one-sided additive error in an insertion-only stream, but it does not enumerate keys by itself. Space-Saving combines counters and candidates for approximate heavy hitters. Always say what can be false: counts, membership, ordering, or ties.

Clarify the contract before naming a data structure

Also distinguish lifetime Top-K from a sliding window. Lifetime counts only increase. A window must expire old events, so an exact design needs a timestamp queue plus decrementable counts, and an approximate design needs a sketch built for windows or deletions. Do not silently reuse an insertion-only proof.

Exact Top-K still needs O(U) frequency state

For a finite prefix containing N events and U distinct keys, the simplest exact design is a hash map. Each ingest increments one counter. At query time, maintain a min-heap of the best k (count, tie-break, key) records seen during a scan of the map.

import heapq
from collections import Counter

def exact_top_k(stream, k):
    counts = Counter(stream)
    if k <= 0:
        return []
    # Simple deterministic reference implementation.
    return sorted(counts, key=lambda x: (-counts[x], x))[:k]

The sort shown is O(U log U) and is useful as an oracle. A size-k selection heap reduces selection to O(U log k), followed by O(k log k) to order the result. The ingest path remains expected O(1), and memory remains O(U).

Keeping only a heap of k keys is not exact. An untracked key can appear repeatedly, pass the current kth count, and deserve entry. Without its historical count, the structure cannot know when that happened. This counterexample is the central reason memory must be discussed before optimization.

Choose where to pay for continuous exact queries

If topK() is called after almost every update, scanning all keys each time is expensive. Several exact designs move more work into add(x):

M in the lazy design counts heap records, not distinct keys. If each increment pushes a new snapshot, stale entries accumulate unless the implementation compacts. Saying “heap size is k” is only true for a query-time selection heap, not for a lazy global heap that preserves old versions.

The candidate-reported Design top-K frequency structure adds decrements and recency tie-breaking. That contract needs explicit item nodes and frequency buckets; a static heap answer does not preserve its promised update and retrieval costs.

Misra–Gries answers a threshold question

With m counters, Misra–Gries processes an insertion-only stream as follows: increment an existing candidate; otherwise insert into an empty counter; otherwise decrement all counters and remove zeros. The summary contains at most m keys.

For a stream of length N, each stored counter underestimates its key's true frequency, and the gap is bounded by the number of global decrement rounds, at most N/(m+1). Any item with frequency greater than N/(m+1) must appear among the candidates. A second pass over a replayable stream can count only those candidates exactly.

That is a heavy-hitter threshold guarantee, not automatically an exact Top-K guarantee. If the kth and (k+1)th items are close, both may fall inside the error band. The algorithm can return candidates without certifying their precise order. Say whether a second pass or source replay is available.

The original Misra–Gries paper addresses values occurring more than a fraction of the input and supplies the foundation for this bounded-candidate approach. The memory limit determines the detectable threshold; k alone does not.

Count-Min Sketch estimates counts but needs candidate discovery

A Count-Min Sketch has d rows and w counters per row. Each update hashes a key once per row and increments those cells. To estimate a known key, read its d cells and return the minimum.

For nonnegative insertion-only updates, collisions can only increase the estimate. With the standard choices w = ceil(e / epsilon) and d = ceil(ln(1 / delta)), a point estimate exceeds the true count by at most approximately epsilon * N with probability at least 1 - delta. The guarantee is additive, not relative: an error of 1,000 is minor for a million-count key and disastrous for a count of 20.

A sketch stores counters, not the original key universe. Therefore it can answer “estimate count for x” but cannot answer “which unseen key is largest?” without a candidate source. Common designs pair it with a bounded candidate heap, a Misra–Gries or Space-Saving summary, or an external dictionary of keys. That second structure must be included in the memory and accuracy analysis.

The Count-Min authors describe point and frequent-item applications with sublinear space. The one-sided guarantee above assumes nonnegative updates; arbitrary negative updates can break the no-underestimate property.

Turn bytes into epsilon and delta

Suppose the counter budget is 64 KiB and counters are 32-bit unsigned integers. That budget holds 65,536 / 4 = 16,384 counters. Choosing d = 7 rows allows w = 2,340 counters per row, using 16,380 counters.

The standard formulas give approximately:

delta ≈ exp(-7) ≈ 0.00091
epsilon ≈ e / 2340 ≈ 0.00116

After N = 1,000,000 inserted events, the additive point-query error is about 1,162 with probability at least 0.99909, under the theorem's hashing assumptions. This arithmetic is a design input, not a promise that Top-K membership is correct. If the true kth and next counts differ by only 200, the bound cannot stabilize their ordering.

Counter width matters too. A 16-bit counter doubles w but overflows at 65,535 unless the design saturates or rescales. Hash seeds, candidate IDs, heap nodes, allocator overhead, and synchronization also consume memory. A good interview estimate distinguishes the clean counter budget from total process memory.

Space-Saving makes candidates part of the summary

Space-Saving maintains a fixed number of (key, estimated count, error) entries. A known key increments its counter. When a new untracked key arrives and all slots are full, it replaces the minimum-count entry and inherits that minimum as its error. The method is designed for frequent and Top-K elements in streams and provides a direct candidate set.

It is often a better answer when the system must continuously report likely heavy hitters rather than estimate arbitrary supplied keys. Its estimates and membership are still approximate. State the error attached to each entry, and do not describe replacement counts as exact observations.

Misra–Gries, Count-Min, and Space-Saving are not interchangeable names for “a sketch.” Misra–Gries emphasizes threshold candidates, Count-Min emphasizes point estimates, and Space-Saving ties bounded counters to candidate discovery. Select from the query contract.

Windows, deletions, distribution, and merging change the design

A last-hour exact Top-K can enqueue (timestamp, key) events, expire them from the front, decrement exact counts, and update the ranking structure. Memory is proportional to the active event window plus active distinct keys. If timestamps arrive out of order, FIFO expiry is insufficient.

For distributed streams, exact maps merge by summing counts for identical keys. Count-Min arrays merge cellwise only when dimensions and hash functions match. Candidate summaries need algorithm-specific merge reasoning; concatenating two local Top-K lists is not generally the global exact Top-K because a moderately frequent key can rank below k on every shard yet win after aggregation.

For negative updates, clarify whether the stream follows a strict turnstile model where counts never go below zero or a general turnstile model. The insertion-only guarantees in this article should not be extended without a deletion-aware algorithm and proof.

Diagnose misleading answers with small adversarial streams

A strong answer names the failure surface before giving code. If the interviewer says “one pass, exact, arbitrary universe, and sublinear memory,” explain the conflict rather than pretending a heap resolves it.

Practice five related PracHub questions

These candidate-reported records provide concrete practice contracts. They do not establish universal frequency, interview order, or employer scoring.

Final takeaway

Start a Streaming Top-K answer with four quantities: stream length N, distinct keys U, requested k, and memory bytes. Then define exactness, query cadence, tie rules, and update model. Exact lifetime Top-K requires retaining every key's count. Bounded memory requires a stated approximation contract and, for sketches such as Count-Min, a separate way to discover candidate keys.

Practice by changing one constraint at a time: query after every event, limit counters to 64 KiB, add a one-hour window, allow decrements, or merge four shards. Continue with the five linked Coding & Algorithms questions and make every complexity statement include the hidden map, heap, candidate IDs, and stale records.

Sources and Further Reading

• Cormode and Muthukrishnan: Count-Min Sketch publication page
• Misra and Gries: Finding Repeated Elements
• UCSB: Efficient Computation of Frequent and Top-k Elements in Data Streams
• PracHub: Find top-K frequent elements in a stream
• PracHub: Answer static and streaming Top-K queries

Research note: Technical papers and PracHub practice records were checked on September 13, 2026. Research sources support the algorithmic guarantees; PracHub records support only the individual practice contracts described above.