Top-K Selection, Heaps, And Ranking

What's being tested

Top-K selection tests whether you can rank, filter, aggregate, and retain only the best candidates without unnecessary full sorting. Interviewers are probing heap usage, tie-breaking correctness, frequency aggregation, and whether your solution adapts from small arrays to streaming or high-volume workloads.

Patterns & templates

• Min-heap of size k — keep current best k items in O(n log k) time; compare with full sort O(n log n).

• Custom comparator tuples — encode ranking as (score, -distance, id) or similar; make tie-breaking explicit and deterministic.

• Hash map plus heap — count with dict / HashMap, then extract top k; total complexity is O(n + m log k).

• Stable selection — when duplicates or leftmost ties matter, preserve original index in the comparator, e.g. (value, -index) or (rank, index).

• Weighted aggregation — normalize keys first, accumulate total_weight[city] += weight, then rank by total and declared tie-break rules.

• SQL ranking template — use GROUP BY, SUM(weight), filtering in WHERE, then ORDER BY score DESC, distance ASC LIMIT k.

• Streaming workload choice — exact top-K uses counters plus heap; heavy-hitter approximations like Count-Min Sketch trade accuracy for memory.

Common pitfalls

Pitfall: Sorting everything when k is small misses the expected O(n log k) optimization and may not scale.

Pitfall: Leaving tie-breaking implicit can fail hidden tests; always state and implement score, distance, index, or lexicographic order rules.

Pitfall: Aggregating before cleaning keys gives wrong winners, especially with inconsistent casing, whitespace, missing fields, or malformed locations.

Practice these

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