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

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

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

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.