Simulate a fixed-capacity least-recently-used cache over get and put operations

Design a cache with a fixed capacity that evicts the least recently used key when it is full. To make it testable as one function, you receive the capacity and a sequence of operations, and you return the results of the `get` operations in order. ### Function Signature ```python def run_lru_cache(capacity: int, operations: list[str], arguments: list[list[int]]) -> list[int]: ``` `operations[i]` is `"get"` or `"put"`, and `arguments[i]` holds its arguments: `[key]` for `"get"` and `[key, value]` for `"put"`. ### Rules - The cache starts empty and holds at most `capacity` keys. - `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 nothing changes. - `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, and then `key` is inserted as the most recently used key. - A key is "used" when it is inserted or updated by `put`, or read by a successful `get`. - Return one integer per `get`, in the order the `get` operations appear. `put` produces no output. ### Constraints - `1 <= capacity <= 3000` - `1 <= len(operations) == len(arguments) <= 2 * 10^5` - `0 <= key <= 10^4` and `0 <= value <= 10^9` - Aim for constant average time per operation. ### Examples **Example 1** ```text Input: capacity = 2, operations = ["put", "put", "get", "put", "get", "put", "get", "get", "get"], arguments = [[1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Output: [1, -1, -1, 3, 4] ``` After the two puts, key `1` is the least recently used. `get(1)` returns `1` and makes key `2` the least recently used, so `put(3, 3)` evicts `2` and `get(2)` returns `-1`. `put(4, 4)` then evicts `1`, so `get(1)` returns `-1`, while `get(3)` and `get(4)` return `3` and `4`. **Example 2** ```text Input: capacity = 2, operations = ["put", "put", "put", "put", "get", "get"], arguments = [[1, 10], [2, 20], [1, 15], [3, 30], [1], [2]] Output: [15, -1] ``` `put(1, 15)` updates an existing key without eviction and makes `1` the most recently used, so `put(3, 30)` evicts `2`. **Example 3** ```text Input: capacity = 1, operations = ["get", "put", "get", "put", "get", "get"], arguments = [[5], [5, 0], [5], [6, 7], [5], [6]] Output: [-1, 0, -1, 7] ``` A stored value of `0` is a hit, not a miss. With capacity `1`, `put(6, 7)` evicts key `5`.