Design a Fixed-Capacity Least-Recently-Used Cache
Company: xAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
# Design a Fixed-Capacity Least-Recently-Used Cache
Design and implement a cache with a fixed maximum capacity that evicts the **least recently used** entry when it is full. Your implementation must support the following operations, each in **O(1) average time**:
- `LRUCache(capacity)` — initialize the cache with a positive integer capacity.
- `get(key)` — return the value associated with `key` if it is present in the cache; otherwise return `-1`. A successful `get` marks the key as the **most recently used** entry.
- `put(key, value)` — insert `key` with `value`. If `key` already exists, update its value and mark it as the most recently used entry. If `key` does not exist and the cache is at capacity, evict the least recently used entry first, then insert the new key as the most recently used entry.
"Recency" is defined by the order of successful `get` calls and all `put` calls: every `get` hit and every `put` (insert or update) makes that key the most recently used; the entry that has gone the longest without being touched by either operation is the least recently used.
Do **not** use a built-in ordered-map structure that already provides LRU behavior (such as Python's `OrderedDict` / `functools.lru_cache` or Java's access-ordered `LinkedHashMap`) as the core of your solution — build the recency-ordering structure yourself.
**Example**
```
LRUCache cache = new LRUCache(2)
cache.put(1, 1) // cache: {1=1}
cache.put(2, 2) // cache: {1=1, 2=2}
cache.get(1) // returns 1; key 1 is now most recently used
cache.put(3, 3) // capacity exceeded: evicts key 2; cache: {1=1, 3=3}
cache.get(2) // returns -1 (evicted)
cache.put(4, 4) // evicts key 1; cache: {3=3, 4=4}
cache.get(1) // returns -1 (evicted)
cache.get(3) // returns 3
cache.get(4) // returns 4
```
**Constraints**
- `1 <= capacity <= 10^4`
- `0 <= key, value <= 10^9`
- Up to `10^5` total calls to `get` and `put`
- `get` and `put` must each run in O(1) average time
Your implementation should behave correctly in all edge cases, including: capacity 1; updating the value of an existing key (which must refresh its recency but must not evict anything); repeatedly touching the entry that is currently least recently used; and evicting when the touched or evicted entry is at either end of your recency ordering.
Quick Answer: This question evaluates a candidate's understanding of data structure design and algorithmic complexity, specifically implementing a fixed-capacity least-recently-used (LRU) cache that maintains recency ordering and supports O(1) average-time get and put operations in the Coding & Algorithms category.
Design and implement a cache with a fixed maximum capacity that evicts the **least recently used** entry when it is full. Each operation must run in **O(1) average time**.
Implement a class `LRUCache` with:
- `LRUCache(capacity)` — initialize with a positive integer capacity.
- `get(key)` — return the value associated with `key` if present, otherwise `-1`. A successful `get` marks the key as the **most recently used** entry.
- `put(key, value)` — insert `key` with `value`. If `key` already exists, update its value and mark it most recently used. If `key` is new and the cache is at capacity, evict the least recently used entry first, then insert the new key as most recently used.
"Recency" is defined by the order of successful `get` calls and all `put` calls: every `get` hit and every `put` (insert or update) makes that key the most recently used; the entry that has gone the longest without being touched by either operation is the least recently used.
Do **not** use a built-in ordered-map that already provides LRU behavior (Python `OrderedDict` / `functools.lru_cache`, Java access-ordered `LinkedHashMap`) as the core — build the recency-ordering structure yourself (the intended solution is a hash map plus a doubly linked list).
**How this console drives your class.** The harness calls a driver `solution(operations, args)`. `operations` is a list of strings (`"LRUCache"`, `"put"`, `"get"`) and `args[i]` holds the arguments for `operations[i]` (`[capacity]`, `[key, value]`, or `[key]`). The driver constructs your `LRUCache`, replays the calls in order, and returns **the list of values produced by the `get` calls** (constructor and `put` produce no output). Implement the `LRUCache` class; the driver is provided for you.
**Example**
```
operations = ["LRUCache","put","put","get","put","get","put","get","get","get"]
args = [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
put(1,1) // cache: {1=1}
put(2,2) // cache: {1=1, 2=2}
get(1) // -> 1; key 1 now most recently used
put(3,3) // at capacity: evict key 2; cache: {1=1, 3=3}
get(2) // -> -1 (evicted)
put(4,4) // evict key 1; cache: {3=3, 4=4}
get(1) // -> -1 (evicted)
get(3) // -> 3
get(4) // -> 4
returns (get results only): [1, -1, -1, 3, 4]
```
Constraints
- 1 <= capacity <= 10^4
- 0 <= key, value <= 10^9
- Up to 10^5 total calls to get and put
- get and put must each run in O(1) average time
- Do not use a built-in access-ordered map (OrderedDict / lru_cache / access-ordered LinkedHashMap) as the core structure
Examples
Input: (['LRUCache','put','put','get','put','get','put','get','get','get'], [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]])
Expected Output: [1, -1, -1, 3, 4]
Explanation: The spec example (capacity 2). get(1) hits (1), then put(3,3) evicts key 2 so get(2)=-1; put(4,4) evicts key 1 so get(1)=-1; get(3)=3 and get(4)=4 remain.
Input: (['LRUCache','put','get','put','get','get'], [[1],[1,1],[1],[2,2],[1],[2]])
Expected Output: [1, -1, 2]
Explanation: Capacity 1 edge case. put(1,1) then get(1)=1; put(2,2) evicts key 1 (the only entry), so get(1)=-1 and get(2)=2.
Hints
- Combine a hash map (key -> node) for O(1) lookup with a doubly linked list that keeps entries ordered by recency; the head end is most recently used, the tail end is least recently used.
- Use two sentinel nodes (a dummy head and dummy tail) so insertion and removal never have to special-case the ends of the list — every real node always has a non-null prev and next.
- On both a get hit and a put on an existing key, unlink the node from its current position and re-insert it right behind the head (most recently used). On eviction, remove the node just before the tail and delete its key from the map.
- When updating an existing key in put, refresh recency but do NOT evict — the size did not grow. Only a brand-new key at full capacity triggers an eviction.