Simulate an LFU cache that evicts the least-used key, breaking ties by recency

Implement a least-frequently-used (LFU) cache with a fixed capacity and simulate a sequence of operations on it. The cache maps integer keys to integer values and keeps a use count for each key. When the cache is full and a new key must be inserted, it evicts the key with the smallest use count; if several keys share that smallest count, it evicts the one among them that was used least recently. Write a function that creates a cache with the given capacity, applies the operations in order, and returns the results of the `get` operations. ### Function Signature ```python def simulate_lfu_cache(capacity: int, ops: List[str], args: List[List[int]]) -> List[int]: ``` ### Rules - `ops[i]` is either `"get"` or `"put"`, and `args[i]` holds its arguments: `[key]` for `get`, `[key, value]` for `put`. - `get(key)`: if the key is present, return its value and count this as one use of the key; otherwise return `-1`. - `put(key, value)` on a key that is present: replace its value and count this as one use of the key. Nothing is evicted. - `put(key, value)` on a new key: if the cache already holds `capacity` keys, first evict one key as described above; then insert the new key with a use count of 1. The insertion counts as the new key's most recent use. - An evicted key loses its use count; if it is inserted again later, it starts again at 1. - "Used least recently" means the key whose latest use (insertion, update or successful `get`) happened earliest. - The result contains one integer per `get`, in order; `put` contributes nothing. ### Constraints - `1 <= capacity <= 10^4` - `1 <= len(ops) == len(args) <= 2 * 10^5` - `0 <= key <= 10^5` - `0 <= value <= 10^9` - The interviewer expects each operation to run in O(1) average time. ### Examples Example 1 ```text Input: capacity = 2 ops = ["put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] args = [[1, 10], [2, 20], [1], [3, 30], [2], [3], [4, 40], [1], [3], [4]] Output: [10, -1, 30, -1, 30, 40] ``` After `get(1)`, key 1 has two uses and key 2 has one, so `put(3, 30)` evicts key 2. After `get(3)`, keys 1 and 3 both have two uses; key 1's latest use is older, so `put(4, 40)` evicts key 1. Example 2 ```text Input: capacity = 1 ops = ["put", "put", "get", "put", "get", "get"] args = [[5, 1], [5, 2], [5], [6, 3], [5], [6]] Output: [2, -1, 3] ``` The second `put` updates key 5 and the `get` brings it to three uses, but with a capacity of 1, inserting key 6 must still evict key 5.