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

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

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

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

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.