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.

Simulate a Least-Recently-Used Key-Value Cache

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.

Implement run_lru_cache(capacity, operations). Each operation is a triple (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.

Each operation is passed as a three-element sequence: a Python tuple, a JavaScript array [op, key, value], a Java java.util.List<Object> holding a String followed by two numbers, or a C++ std::tuple<std::string, int, int>.

Constraints

• 1 <= capacity <= 10^5
• 1 <= len(operations) <= 2 * 10^5
• Every operation is either ("get", key, 0) or ("put", key, value).
• 0 <= key <= 10^9
• 0 <= value <= 10^9, so -1 never collides with a stored value.
• Every key, value and result fits in a signed 32-bit integer; no value exceeds 2^31 - 1.

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.

Hints

1. Each operation needs two things quickly: the value currently stored under a key, and which stored entry has gone longest without a successful get or a put.
2. Only a successful get or a put changes an entry's recency. A missed get changes nothing, and overwriting a key that is already stored never evicts.
3. Eviction happens only when a key that is not already stored arrives while the cache already holds capacity entries.

Approach

Keep a hash map from key to stored value together with a recency order of the stored entries, least recently used first. Python's OrderedDict, Java's access-ordered LinkedHashMap, JavaScript's insertion-ordered Map (delete and re-insert to refresh) and a C++ std::list indexed by an unordered_map of iterators all give O(1) average lookup, move-to-most-recent and removal of the least recent entry.

Invariant: after every operation the map holds exactly the cached keys, at most capacity of them, and the order lists them by the time of their latest successful get or put.

• get on a stored key: move the entry to the most recent end and record its value. get on a missing key: record -1 and touch nothing, so recency is unchanged.
• put on a stored key: overwrite the value and move the entry to the most recent end. The size does not change, so nothing is evicted.
• put on a new key: if the cache already holds capacity entries, remove the entry at the least recent end, which by the invariant is exactly the least recently used one, then append the new entry at the most recent end.

Each branch preserves the invariant, so every recorded lookup matches the rules, and results are appended in the order the gets appear.

Edge cases: capacity 1 (every new key evicts the previous one), no gets (empty list), gets on an empty cache (-1 each), a stored value 0 (membership is tested explicitly, so 0 is never mistaken for the -1 miss), filling exactly to capacity (no eviction until a further new key arrives), and keys or values up to 10^9, which fit in 32-bit integers.

• Time complexity: O(n) for n operations, O(1) average per operation
• Space complexity: O(min(capacity, n)) for the cache, plus O(n) for the returned list