Simulate a Least-Frequently-Used Cache with Recency Tie-Breaking

This follows a least-recently-used cache problem. Now the fixed-capacity cache, when full, evicts the key that has been used the fewest times, and breaks ties between such keys by recency. Simulate it over a sequence of `get` and `put` operations and return the result of every `get`. ### Function Signature ```python def simulate_lfu_cache(capacity: int, operations: list[str], arguments: list[list[int]]) -> list[int]: ``` ### Rules - The cache starts empty and never holds more than `capacity` keys. Every key in the cache has a use count. - `operations[i]` is `"get"` or `"put"`, and `arguments[i]` holds that operation's arguments. - `"get"` with `[key]`: if `key` is in the cache, the result is its value and its use count increases by 1. Otherwise the result is `-1` and nothing changes. - `"put"` with `[key, value]`: if `key` is in the cache, replace its value and increase its use count by 1. Otherwise, if the cache already holds `capacity` keys, first evict one key, then insert `key` with `value` and a use count of 1. A `put` produces no result. - The evicted key is the one with the smallest use count. If several keys share that smallest count, evict the one among them whose latest successful `get` or latest `put` happened earliest. - An evicted key's count is discarded: if the key is put again later, it starts again at a count of 1. - Return one integer per `"get"`, in the order the operations appear. - The intended solution handles every operation in O(1) average time. ### Constraints - `1 <= capacity <= 3000` - `1 <= len(operations) == len(arguments) <= 2 * 10^5` - `arguments[i]` has length 1 when `operations[i]` is `"get"` and length 2 when it is `"put"`. - `0 <= key <= 10^4` - `0 <= value <= 10^9`, so a stored value is never `-1`, and every number, including every use count, fits in a 32-bit signed integer. ### Examples **Example 1** ```text Input: capacity = 2 operations = ["put", "put", "get", "get", "put", "get", "get", "put", "get", "get", "get"] arguments = [[1, 100], [2, 200], [1], [1], [3, 300], [2], [3], [4, 400], [1], [3], [4]] Output: [100, 100, -1, 300, 100, -1, 400] ``` After two reads, key `1` has count 3 and key `2` has count 1, so `put 3` evicts key `2`. One read raises key `3` to count 2, still below key `1`, so `put 4` evicts key `3`. **Example 2** ```text Input: capacity = 3 operations = ["put", "put", "put", "get", "get", "get", "put", "get", "get", "get", "get"] arguments = [[1, 10], [2, 20], [3, 30], [3], [2], [1], [4, 40], [3], [1], [2], [4]] Output: [30, 20, 10, -1, 10, 20, 40] ``` All three keys have count 2 when key `4` arrives. Key `3` was inserted last but read first, so it is the least recently used of the three and is evicted. **Example 3** ```text Input: capacity = 2 operations = ["put", "put", "get", "put", "put", "get", "get", "get"] arguments = [[1, 1], [2, 2], [2], [1, 5], [3, 3], [1], [2], [3]] Output: [2, 5, -1, 3] ``` Updating key `1` counts as a use, so keys `1` and `2` both have count 2 when key `3` arrives. Key `2` was used less recently and is evicted.