Simulate a Fixed-Capacity Cache With Least-Recently-Used Eviction

A cache holds at most `capacity` key-value pairs. When a new key must be inserted into a full cache, the cache first evicts the key that was used least recently. Process a sequence of `get` and `put` operations on an initially empty cache and return the result of every `get`, in order. ### Function Signature ```python def lru_get_results(capacity: int, operations: list[list[int]]) -> list[int]: ``` ### Rules - Each operation is a list of integers. A list of length 1, `[key]`, is `get(key)`; a list of length 2, `[key, value]`, is `put(key, value)`. - `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 evicted first; then `key` is inserted with `value` as the most recently used key. - A key's recency changes only when a `get` finds it or a `put` writes it. A `get` that misses changes nothing. - Return a list with one integer per `get` operation, in the order the operations appear. `put` operations add nothing to it. If there is no `get`, return an empty list. - Each `get` and `put` should run in $O(1)$ average time. ### Constraints - `1 <= capacity <= 10^5` - `1 <= len(operations) <= 2 * 10^5` - `0 <= key <= 10^9` - `0 <= value <= 10^9`, so a result of `-1` always means the key was not found. - All values fit in a signed 32-bit integer. ### Examples **Example 1** ```text Input: capacity = 2 operations = [[5, 50], [7, 70], [5], [9, 90], [7], [5], [9]] Output: [50, -1, 50, 90] ``` After the two puts, the cache holds 5 and 7, with 5 the least recently used. `get(5)` returns 50 and makes 7 the least recently used, so `put(9, 90)` evicts 7. `get(7)` then returns -1, `get(5)` returns 50 and `get(9)` returns 90. **Example 2** ```text Input: capacity = 2 operations = [[1, 10], [2, 20], [1, 15], [3, 30], [1], [2], [3]] Output: [15, -1, 30] ``` `put(1, 15)` updates an existing key without evicting anything and makes 1 the most recently used, so `put(3, 30)` evicts 2. The gets return 15, -1 and 30. **Example 3** ```text Input: capacity = 1 operations = [[4], [4, 0], [4], [6, 1], [4], [6]] Output: [-1, 0, -1, 1] ``` The first `get(4)` misses on the empty cache. After `put(4, 0)`, `get(4)` returns the stored value 0. `put(6, 1)` evicts 4 from the one-slot cache, so `get(4)` misses and `get(6)` returns 1.