Quick Overview

Design a fixed-capacity least-recently-used cache as an object-oriented exercise, driven here by a list of get and put operations whose read results you return. Tests O(1) lookup, recency updates on reads and writes, and correct eviction order.

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

Company: Waymo

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

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 ```python 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]`

Overview: Design a fixed-capacity least-recently-used cache as an object-oriented exercise, driven here by a list of get and put operations whose read results you return. Tests O(1) lookup, recency updates on reads and writes, and correct eviction order.

Implement a fixed-capacity least-recently-used (LRU) cache and drive it with a list of operations. The cache starts empty and holds at most `capacity` entries. Process `operations[i]` together with `arguments[i]`, in order, for every index `i`: - `"get"` with arguments `[key]`: if `key` is in the cache, the result of this operation is its value and the entry becomes the most recently used. Otherwise the result is `-1` and the cache is left unchanged (a miss does not change anyone's recency). - `"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 insert into a cache holding fewer than `capacity` entries never evicts anything. An entry's recency is refreshed by every successful `get` of its key and by every `put` of its key. Both operations should run in O(1) average time. Return a list with the result of every `"get"` operation, in the order the operations appear. If there is no `"get"` operation, return an empty list. Function signature: `run_lru_cache(capacity, operations, arguments)` returning a list of integers. (In the JavaScript starter the third parameter is named `args`, because `arguments` is reserved inside JavaScript functions.) Constraints: - `1 <= capacity <= 10^4` - `1 <= len(operations) == len(arguments) <= 2 * 10^5` - Each `operations[i]` is exactly `"get"` or `"put"`. - `arguments[i]` is `[key]` when `operations[i]` is `"get"` and `[key, value]` when it is `"put"`. - `0 <= key <= 10^9` and `0 <= value <= 10^9`, so every key, value and result fits in a signed 32-bit integer. 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.

Constraints

  • 1 <= capacity <= 10^4
  • 1 <= len(operations) == len(arguments) <= 2 * 10^5
  • Each operations[i] is exactly "get" or "put"
  • arguments[i] is [key] for "get" and [key, value] for "put"
  • 0 <= key <= 10^9
  • 0 <= value <= 10^9

Examples

Input: (2, ['put', 'put', 'get', 'put', 'get', 'get', 'put', 'get', 'get'], [[1, 10], [2, 20], [1], [3, 30], [2], [3], [1, 11], [1], [3]])

Expected Output: [10, -1, 30, 11, 30]

Input: (2, ['put', 'put', 'put', 'get', 'put', 'get', 'get'], [[4, 1], [5, 2], [4, 3], [5], [6, 4], [4], [5]])

Expected Output: [2, -1, 2]

Hints

  1. You need two things in O(1): find an entry by key, and find the entry that was used longest ago. One data structure alone does not give you both.
  2. Think of the recency order as a line where every successful get or any put of a key moves that key to the back, so the front is always the next eviction victim.
  3. A miss on get must not change the order, and a put of an existing key updates in place without evicting even when the cache is full.

Loading coding console...

Show the approach

Approach

Keep two structures in sync: a hash map from key to its entry, and a recency order in which the front is the least recently used entry and the back is the most recently used one. A doubly linked list (or an insertion-ordered map such as Python's OrderedDict or JavaScript's Map) gives O(1) removal of any entry and O(1) append at the back.

For "get", look the key up in the map. On a miss, record -1 and touch nothing. On a hit, move the entry to the back of the order and record its value.

For "put", if the key exists, overwrite the value and move the entry to the back; the size does not change, so nothing is evicted. If the key is new and the cache already holds capacity entries, remove the front entry from both the order and the map first, then append the new entry at the back and register it in the map. Because the front of the order is always the entry whose last successful get or put is oldest, this evicts exactly the least recently used entry.

Every operation does a constant number of hash lookups and list relinks, so each runs in O(1) average time. The Java reference stores the linked list in index arrays with a sentinel slot, and the C++ reference uses std::list::splice to move a node to the back without reallocating.

Time complexity:
O(n) total for n operations (O(1) average per get or put)
Space complexity:
O(min(capacity, n)) for the cache, plus O(n) for the returned results