#238HardDesign· Frequency Buckets with Recency Order

LFU Cache Design

A content server keeps a fixed number of popular items in memory. Evicting the item used longest ago (an LRU policy) can throw away an item that is requested constantly just because a burst of one-off requests arrived. This server instead evicts the **least frequently used** item. Design a class `LFUCache`: - `LFUCache(capacity)` creates a cache holding at most `capacity` items. - `get(key)` returns the value stored for `key` and counts as one use of it, or returns `-1` if the key is not in the cache. - `put(key, value)` stores or updates the value of `key` and counts as one use. If storing a new key would exceed the capacity, first evict the item with the **smallest use count**; if several items share that count, evict the **least recently used** among them. A newly stored item starts with a use count of 1. With capacity 0 nothing is ever stored. Both operations must run in O(1) average time.

Input format

`operations`: the method names in call order (the first is the constructor); `arguments`: the argument list of each call.

Output format

One value per operation: `null` for the constructor and for `put`, and the value (or -1) for each `get`.

Examples

Input: operations = ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"], arguments = [[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]

Output: [null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Keys 1 and 2 are stored; get(1) raises key 1 to two uses. put(3) must evict: key 2 has one use, key 1 has two, so key 2 goes and get(2) returns -1. get(3) gives key 3 two uses. put(4) evicts the one with fewer uses among 1 and 3: both have two, and key 1 was used less recently, so 1 is evicted. The remaining gets return -1, 3 and 4.

Input: operations = ["LFUCache", "put", "get", "put", "get"], arguments = [[0], [1, 5], [1], [2, 6], [2]]

Output: [null, null, -1, null, -1]

A cache of capacity zero stores nothing, so every get returns -1.

Constraints

0 <= capacity <= 10^4
0 <= key <= 10^5
0 <= value <= 10^9
At most 2 * 10^5 calls in total.