Top-K Frequency Tracking
Asked of: Software Engineer
Last updated
What's being tested
This tests in-memory data structure design for maintaining top- items under frequent updates, deletes, ties, and churn. Interviewers expect clear tradeoffs between heap, balanced tree, bucketed linked list, and hash map approaches, with precise complexity and edge-case handling.
Patterns & templates
-
Hash map + min-heap —
O(log K)updates for approximate top- candidates; lazy-delete stale heap entries after frequency changes. -
Hash map + balanced tree — store
(freq, recency, key)inTreeSet/SortedDict; update by remove-then-reinsert inO(log n). -
Bucketed doubly linked list — map frequency to bucket node; move keys between adjacent buckets in amortized
O(1)for increment/decrement. -
AllOne-style structure —
key -> bucket, bucket hasfreqand key set/list; supportsinc,dec,getMaxKey,getMinKey. -
Top-K query strategy — scan buckets from max frequency downward until
Kkeys collected;O(K + number_of_buckets_visited). -
Tie-breaking by recency — maintain monotonic timestamp/counter; compare
(freq DESC, lastUpdated DESC, key)and update tie fields consistently. -
Concurrency template — start with one lock for correctness; discuss striped locks or actor/sharded ownership only after API semantics are clear.
Common pitfalls
Pitfall: Updating frequency in-place inside a heap or tree without removing the old ordering entry breaks ordering invariants.
Pitfall: Claiming
O(1)top- because increments areO(1); returning arbitrary max-frequency keys may still require traversal.
Pitfall: Ignoring delete/decrement semantics under zero counts causes memory leaks and stale keys during high-churn workloads.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Design a Real-Time Top-K Ranking SystemUber · Software Engineer · Onsite · hard
- Design top-K frequency structureUber · Software Engineer · Onsite · Medium
- Implement rate limiter, top-K, scheduler algorithmsUber · Software Engineer · Onsite · Medium
- Design top-K tracker with linked listsUber · Software Engineer · Onsite · Medium
Related concepts
- Top-K Queries And Streaming AggregationCoding & Algorithms
- Top-K Ranking And SelectionSystem Design
- Top-K Selection, Heaps, And RankingCoding & Algorithms
- Top-K, Heaps, Quickselect, And Frequency AnalysisCoding & Algorithms
- Heaps, Priority Queues, and Top-K SelectionCoding & Algorithms
- Real-Time Top-K And Streaming AnalyticsSystem Design