Top-K Frequency Tracking

What's being tested

This tests in-memory data structure design for maintaining top-$K$ 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-$K$ candidates; lazy-delete stale heap entries after frequency changes.

• Hash map + balanced tree — store (freq, recency, key) in TreeSet/SortedDict; update by remove-then-reinsert in O(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 has freq and key set/list; supports inc, dec, getMaxKey, getMinKey.

• Top-K query strategy — scan buckets from max frequency downward until K keys 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-$K$ because increments are O(1); returning arbitrary $K$ 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.