Fixed-Capacity Cache That Evicts the Least Frequently Used Key, Ties by Recency

Implement a key-value cache with a fixed capacity that, when it is full and a new key has to be inserted, evicts the key that has been used the fewest times. If several keys share the smallest use count, it evicts the one among them 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

def simulate_lfu_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

• Every key in the cache has a use count.
• get(key): if key is in the cache, the result is its value, its use count increases by 1, and it 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, its use count increases by 1, and it becomes the most recently used key; nothing is evicted. Otherwise, if the cache already holds capacity keys, one key is evicted first: the key with the smallest use count, and among keys tied for the smallest count, the least recently used one. Then key is inserted with value and a use count of 1, and it becomes the most recently used key.
• An evicted key loses its count. If it is inserted again later, its count starts again at 1.
• 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

Input: capacity = 3,
 operations = ["put", "put", "put", "get", "get", "put", "get", "get", "put", "get", "put", "put", "get", "get", "get"],
 arguments = [[1, 100], [2, 200], [3, 300], [2], [3], [4, 400], [1], [4], [5, 500], [2], [3, 333], [6, 600], [5], [3], [6]]
Output: [200, 300, -1, 400, -1, -1, 333, 600]

Key 1 is the only key never read, so put(4, 400) evicts it. Just before put(5, 500), keys 2, 3 and 4 all have a use count of 2, and key 2 was used least recently, so it is evicted. put(3, 333) updates key 3 and raises its count to 3. Just before put(6, 600), key 5 has the smallest count, 1, and is evicted.

Example 2

Input: capacity = 1,
 operations = ["put", "get", "put", "get", "get"],
 arguments = [[1, 1], [1], [2, 2], [1], [2]]
Output: [1, -1, 2]

With room for one key, put(2, 2) evicts key 1 even though key 1 has the higher use count, because it is the only key in the cache.

Example 3

Input: capacity = 2,
 operations = ["put", "get", "put", "get", "get", "get", "put", "put", "put", "get", "get", "get"],
 arguments = [[1, 1], [1], [2, 2], [2], [2], [1], [3, 3], [2, 20], [4, 4], [1], [2], [4]]
Output: [1, 2, 2, 1, 1, -1, 4]

Keys 1 and 2 both reach a use count of 3, and key 2 was used less recently, so put(3, 3) evicts key 2. put(2, 20) evicts key 3, whose count is 1, and key 2 comes back with a count of 1 rather than its old count, so put(4, 4) evicts key 2 instead of key 1.