Fixed-Capacity Cache That Evicts the Least Frequently Used Key, Ties by Recency

Implement a key-value cache with a fixed capacity that, when it is full and a new key has to be inserted, evicts the key that has been used the fewest times. If several keys share the smallest use count, it evicts the one among them that was used least recently. The cache is tested through one function: it receives the capacity and a sequence of operations, applies them in order to an initially empty cache, and returns the results of the read operations. ### Function Signature ```python def simulate_lfu_cache(capacity: int, operations: list[str], arguments: list[list[int]]) -> list[int]: ``` `operations[i]` is `"get"` or `"put"`. For `"get"`, `arguments[i]` is `[key]`; for `"put"`, it is `[key, value]`. ### Rules - Every key in the cache has a use count. - `get(key)`: if `key` is in the cache, the result is its value, its use count increases by 1, and it becomes the most recently used key. Otherwise the result is `-1` and the cache does not change. - `put(key, value)`: if `key` is already in the cache, its value is replaced, its use count increases by 1, and it becomes the most recently used key; nothing is evicted. Otherwise, if the cache already holds `capacity` keys, one key is evicted first: the key with the smallest use count, and among keys tied for the smallest count, the least recently used one. Then `key` is inserted with `value` and a use count of 1, and it becomes the most recently used key. - An evicted key loses its count. If it is inserted again later, its count starts again at 1. - Return one integer per `"get"` operation, in the order the operations appear. `"put"` operations produce no output. - Each operation must run in $O(1)$ average time. ### Constraints - `1 <= capacity <= 10^4` - `1 <= len(operations) <= 2 * 10^5`, and `len(arguments) == len(operations)` - `0 <= key <= 10^5` - `0 <= value <= 10^9` - Every operation is `"get"` or `"put"`, with the matching number of arguments. ### Examples **Example 1** ```text Input: capacity = 3, operations = ["put", "put", "put", "get", "get", "put", "get", "get", "put", "get", "put", "put", "get", "get", "get"], arguments = [[1, 100], [2, 200], [3, 300], [2], [3], [4, 400], [1], [4], [5, 500], [2], [3, 333], [6, 600], [5], [3], [6]] Output: [200, 300, -1, 400, -1, -1, 333, 600] ``` Key 1 is the only key never read, so `put(4, 400)` evicts it. Just before `put(5, 500)`, keys 2, 3 and 4 all have a use count of 2, and key 2 was used least recently, so it is evicted. `put(3, 333)` updates key 3 and raises its count to 3. Just before `put(6, 600)`, key 5 has the smallest count, 1, and is evicted. **Example 2** ```text Input: capacity = 1, operations = ["put", "get", "put", "get", "get"], arguments = [[1, 1], [1], [2, 2], [1], [2]] Output: [1, -1, 2] ``` With room for one key, `put(2, 2)` evicts key 1 even though key 1 has the higher use count, because it is the only key in the cache. **Example 3** ```text Input: capacity = 2, operations = ["put", "get", "put", "get", "get", "get", "put", "put", "put", "get", "get", "get"], arguments = [[1, 1], [1], [2, 2], [2], [2], [1], [3, 3], [2, 20], [4, 4], [1], [2], [4]] Output: [1, 2, 2, 1, 1, -1, 4] ``` Keys 1 and 2 both reach a use count of 3, and key 2 was used less recently, so `put(3, 3)` evicts key 2. `put(2, 20)` evicts key 3, whose count is 1, and key 2 comes back with a count of 1 rather than its old count, so `put(4, 4)` evicts key 2 instead of key 1.