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.