Design top-K frequency structure
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Design an in-memory data structure that supports: add(x) to observe an item, inc(x) to increment its frequency, dec(x) to decrement (deleting when zero), and topK(k) to return the k items with highest frequency, breaking ties by most recent update. Target O(
1) amortized updates and O(k) retrieval using hash maps plus a doubly linked list of frequency buckets. Describe node layout, how buckets are created/merged, how recency is tracked, tie-breaking, memory bounds under churn, and concurrency considerations.
Quick Answer: This question evaluates ability to design efficient in-memory data structures for frequency tracking, including handling recency-based tie-breaking, memory bounds under churn, and concurrency implications.
Design an in-memory structure that tracks item frequencies and answers top-K queries. You will implement a single driver function `solution(operations)` that replays a list of operations against the structure and returns the result of every `topK` query, in order.
Each operation is a 2-element list:
- `["add", x]` — observe item `x` (increments its frequency by 1, creating it if absent).
- `["inc", x]` — increment the frequency of `x` by 1 (creating it if absent). Semantically identical to `add`.
- `["dec", x]` — decrement the frequency of `x` by 1; when its frequency reaches 0 the item is deleted. A `dec` on an unknown item is a no-op.
- `["topK", k]` — return the `k` items with the highest frequency. **Ties are broken by most-recent update** (the item updated more recently comes first). If fewer than `k` items exist, return all of them.
Return a list containing the result list of each `topK` operation, in the order the `topK` operations appear.
A recency 'update' is any `add`, `inc`, or any `dec` that does NOT delete the item. The intended efficient design uses a hash map of item -> node plus a doubly linked list of frequency buckets (each bucket a recency-ordered list of items) to get O(1) amortized updates and O(k) retrieval; the reference here uses a clear simulation, but your console solution may implement the bucket-list design.
Example: operations `[["add","a"],["add","b"],["inc","a"],["topK",2]]` → `[["a","b"]]` because `a` has frequency 2 and `b` has frequency 1.
Constraints
- 1 <= number of operations <= 10^5
- Items are strings; k is a non-negative integer
- A 'dec' on an item not currently present is a no-op
- An item is deleted exactly when its frequency reaches 0
- Tie-break among equal frequencies is by most-recent update (recency descending)
- topK with k greater than the number of live items returns all live items
Examples
Input: ([['add', 'a'], ['add', 'b'], ['inc', 'a'], ['topK', 2]],)
Expected Output: [['a', 'b']]
Explanation: a is incremented to frequency 2, b stays at 1, so a outranks b.
Input: ([['inc', 'x'], ['inc', 'y'], ['inc', 'y'], ['inc', 'z'], ['inc', 'z'], ['topK', 1]],)
Expected Output: [['z']]
Explanation: x=1, y=2, z=2; y and z tie at frequency 2, but z was updated most recently, so topK(1) returns z.
Hints
- Track two maps: item -> frequency and item -> a monotonically increasing recency stamp. Bump the recency stamp on every add/inc and on every dec that does not delete the item.
- For O(1) amortized updates, keep a doubly linked list of frequency buckets; each bucket holds the items at that frequency in recency order, so inc/dec moves an item to an adjacent bucket in constant time.
- When sorting for topK, the key is (frequency descending, recency descending). The optimal retrieval walks buckets from the highest frequency downward, taking items front-to-back until k are collected.