Top-K Queries And Streaming Aggregation

What's being tested

This tests streaming aggregation and Top-K query design: maintaining counts, sums, balances, or revenues while processing events incrementally. Interviewers are probing whether you can choose between full sort, heap, ordered set, hash map aggregation, and time-window indexing while preserving correctness under ties, updates, and edge cases.

Patterns & templates

• Hash map aggregation — use dict[key] += value for counts, revenue, balances, or per-restaurant totals; O(n) build, O(m) space.

• Top-K via min-heap — maintain heap of size k; O(n log k) time, better than full O(n log n) sorting when k << n.

• Top-K via sorting — aggregate first, then sorted(items, key=(-metric, tie_breaker))[:k]; simple, deterministic, acceptable for moderate m.

• Ordered ranking with ties — define comparator explicitly: higher metric first, then lexicographic ID, timestamp, or insertion order; avoid nondeterministic output.

• Time-window aggregation — filter by start <= ts < end, or maintain deque/prefix sums for repeated range queries; watch inclusive/exclusive boundaries.

• Streaming updates — for changing scores, use lazy heap entries (score, id, version) and discard stale records on pop; avoids expensive heap deletion.

• SQL Top-K template — GROUP BY entity, compute SUM(...), then ORDER BY metric DESC, entity ASC LIMIT k; use ROW_NUMBER() for per-group Top-K.

Common pitfalls

Pitfall: Computing Top-K directly on raw events instead of aggregating by entity first; this ranks orders, not restaurants/users/accounts.

Pitfall: Ignoring tie-breaking; Coinbase-style coding prompts often expect deterministic output even when metrics are equal.

Pitfall: Using full recomputation for every query when repeated streaming queries require incremental maps, heaps, prefix sums, or window indexes.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.