Fixed-Capacity Least-Recently-Used Cache Driven by Get and Put Operations

Design a least-recently-used (LRU) cache. In the interview this was an object-oriented design round: design a cache class with a fixed capacity that supports reading a key and writing a key-value pair, evicting the least recently used entry when it is full. Both operations should run in O(1) average time.

For this console version, the cache is driven by a list of operations and you return the results of the reads.

Function Signature

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

Rules

• Start with an empty cache that holds at most capacity entries. Process operations[i] with arguments[i], in order.
• "get" with arguments [key]: if key is in the cache, the result is its value and the entry becomes the most recently used. Otherwise the result is -1 and the cache is unchanged.
• "put" with arguments [key, value]: if key is already in the cache, replace its value and make it the most recently used; nothing is evicted. Otherwise, if the cache already holds capacity entries, first remove the least recently used entry, then insert the new entry as the most recently used.
• An entry's recency is updated by every successful get and every put of its key.
• Return the results of all "get" operations, in order.

Constraints

• 1 <= capacity <= 10^4
• 1 <= len(operations) == len(arguments) <= 2 * 10^5
• Each operation is "get" or "put".
• 0 <= key <= 10^9 and 0 <= value <= 10^9.

Examples

Example 1

• Input: capacity = 2, operations = ["put", "put", "get", "put", "get", "get", "put", "get", "get"], arguments = [[1, 10], [2, 20], [1], [3, 30], [2], [3], [1, 11], [1], [3]]
• Output: [10, -1, 30, 11, 30]
• Explanation: Reading key 1 makes key 2 the least recently used, so inserting key 3 evicts key 2. Writing key 1 again updates its value without evicting anything.

Example 2

• Input: capacity = 2, operations = ["put", "put", "put", "get", "put", "get", "get"], arguments = [[4, 1], [5, 2], [4, 3], [5], [6, 4], [4], [5]]
• Output: [2, -1, 2]
• Explanation: Updating key 4 makes it the most recently used, but reading key 5 afterwards makes key 4 the least recently used again, so inserting key 6 evicts key 4.

Example 3

• Input: capacity = 1, operations = ["get", "put", "put", "get", "get"], arguments = [[5], [5, 7], [6, 8], [5], [6]]
• Output: [-1, -1, 8]