Fixed-Capacity Key-Value Cache That Evicts the Least Recently Used Key

Implement a key-value cache with a fixed capacity. When the cache is full and a new key has to be inserted, the cache evicts the key 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_lru_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 - `get(key)`: if `key` is in the cache, the result is its value, and `key` 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 and it becomes the most recently used key; nothing is evicted. Otherwise, if the cache already holds `capacity` keys, the least recently used key is removed first; then `key` is inserted with `value` and becomes the most recently used key. - A key is used by every `put` on it and by every `get` that finds it. A `get` that misses does not count as a use. - 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 = 2, operations = ["put", "put", "get", "put", "get", "get", "put", "get", "put", "get", "get"], arguments = [[1, 10], [2, 20], [1], [3, 30], [2], [3], [1, 15], [1], [4, 40], [3], [1]] Output: [10, -1, 30, 15, -1, 15] ``` After the first two operations the cache holds keys 1 and 2, with key 1 the least recently used. `get(1)` returns 10 and makes key 2 the least recently used, so `put(3, 30)` evicts key 2 and `get(2)` returns -1. `get(3)` returns 30. `put(1, 15)` replaces key 1's value without evicting anything and makes key 3 the least recently used; `get(1)` returns 15. `put(4, 40)` evicts key 3, so `get(3)` returns -1, and `get(1)` returns 15. **Example 2** ```text Input: capacity = 1, operations = ["put", "put", "get", "put", "get", "get"], arguments = [[5, 1], [5, 2], [5], [6, 3], [5], [6]] Output: [2, -1, 3] ``` The second `put` on key 5 replaces its value and evicts nothing. With room for one key, `put(6, 3)` evicts key 5. **Example 3** ```text Input: capacity = 2, operations = ["get", "put", "put", "get", "get", "put", "get", "get", "get"], arguments = [[7], [7, 0], [8, 1], [7], [9], [9, 2], [8], [7], [9]] Output: [-1, 0, -1, -1, 0, 2] ``` Reading key 7 makes key 8 the least recently used. The miss on key 9 changes nothing, so `put(9, 2)` evicts key 8. A stored value of 0 is returned as 0.