Simulate a Fixed-Capacity Least-Recently-Used Cache over a Stream of Operations

Implement a key-value cache that holds at most capacity entries and, when it is full, evicts the entry that was used least recently. Run the cache over a list of operations and return the results of the lookups.

Function Signature

def run_lru_cache(capacity: int, operations: list[tuple[str, int, int]]) -> list[int]:

Each operation is a tuple (op, key, value):

• ("get", key, 0) looks up key. The third field is unused and is always 0.
• ("put", key, value) stores value under key.

Rules

• The cache starts empty.
• get: if key is in the cache, the result is its value and the entry becomes the most recently used one. Otherwise the result is -1 and the cache does not change.
• put of a key that is already in the cache replaces its value and makes the entry the most recently used one; nothing is evicted.
• put of a new key adds it as the most recently used entry. If the cache already holds capacity entries, first evict the least recently used entry, then add the new one.
• An entry's recency is the time of its latest successful get or of the latest put of its key.
• Return one integer per get, in the order the get operations appear. Return an empty list if there are none.
• Aim for O(1) average time per operation.

Constraints

• 1 <= capacity <= 10^5
• 1 <= len(operations) <= 2 * 10^5
• 0 <= key <= 10^9
• 0 <= value <= 10^9, so -1 never collides with a stored value.

Examples

Example 1

Input: capacity = 2
 operations = [("put", 1, 10), ("put", 2, 20), ("get", 1, 0), ("put", 3, 30),
 ("get", 2, 0), ("get", 3, 0), ("get", 1, 0)]
Output: [10, -1, 30, 10]

After the two puts, key 1 is the least recently used. get(1) returns 10 and makes key 2 the least recently used, so put(3) evicts key 2. The later lookups return -1 for key 2, then 30 and 10.

Example 2

Input: capacity = 2
 operations = [("put", 1, 1), ("put", 2, 2), ("put", 1, 5), ("put", 3, 3),
 ("get", 1, 0), ("get", 2, 0), ("get", 3, 0)]
Output: [5, -1, 3]

put(1, 5) updates key 1 without evicting anything and makes it the most recently used, so put(3) evicts key 2.

Example 3

Input: capacity = 1
 operations = [("get", 7, 0), ("put", 7, 70), ("put", 8, 80), ("get", 7, 0), ("get", 8, 0)]
Output: [-1, -1, 80]

The first lookup misses on an empty cache. With room for one entry, put(8) evicts key 7.