Design top-K frequency structure

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.

Design top-K frequency structure

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

Hints

1. 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.
2. 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.
3. 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.