Implement an LRU cache
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
## Problem: LRU Cache
Design and implement a data structure that supports an **LRU (Least Recently Used) cache** with a fixed capacity.
### Requirements
Implement a cache with the following operations:
- `get(key) -> value`
- If `key` exists in the cache, return its value and mark the entry as **most recently used**.
- If `key` does not exist, return `-1`.
- `put(key, value) -> void`
- Insert or update the `(key, value)` pair.
- If inserting causes the number of keys to exceed `capacity`, evict the **least recently used** entry.
- Updating an existing key should also mark it as **most recently used**.
### Performance Constraints
- Target time complexity: **O(1)** average for both `get` and `put`.
- Space complexity: **O(capacity)**.
### Example
Assume `capacity = 2`:
- `put(1, 10)`
- `put(2, 20)`
- `get(1) -> 10` (now key `1` is most recently used)
- `put(3, 30)` (evicts key `2` as least recently used)
- `get(2) -> -1`
### Notes
You may choose any programming language, but clearly describe the data structures you use and how you ensure O(1) operations.
Quick Answer: This question evaluates understanding of cache design and eviction policies (LRU), along with competency in selecting and reasoning about data structures and complexity to support efficient get and put operations under capacity constraints.
Design and implement a data structure that supports an **LRU (Least Recently Used) cache** with a fixed `capacity`, supporting two operations in O(1) average time:
- `get(key)` — return the value if `key` is present and mark it **most recently used**; otherwise return `-1`.
- `put(key, value)` — insert or update the pair and mark it **most recently used**; if this makes the number of keys exceed `capacity`, evict the **least recently used** entry.
To make this runnable, your function is given the `capacity` and a list of `operations`. Replay them against your cache and return a list containing the result of every `get` operation, in order.
**Operation encoding**
- `put`: `["put", key, value]` — performs `put(key, value)`, produces no output.
- `get`: `["get", key]` — performs `get(key)`, appends its return value (the value, or `-1`) to the output list.
**Example** (`capacity = 2`)
Operations: `[["put",1,10], ["put",2,20], ["get",1], ["put",3,30], ["get",2], ["get",3]]`
- `put(1,10)`, `put(2,20)` → cache `{1:10, 2:20}`
- `get(1)` → `10` (key 1 now most recently used)
- `put(3,30)` → exceeds capacity, evict least recently used key `2` → `{1:10, 3:30}`
- `get(2)` → `-1` (evicted)
- `get(3)` → `30`
Return: `[10, -1, 30]`.
Aim for O(1) average per operation using a hash map plus a doubly linked list (or an ordered map).
Constraints
- 1 <= capacity
- 0 <= number of operations
- Keys and values are integers
- get on a missing key returns -1
- put that updates an existing key marks it most recently used and does NOT evict
- Both get and put must be O(1) average time
Examples
Input: (2, [['put', 1, 10], ['put', 2, 20], ['get', 1], ['put', 3, 30], ['get', 2], ['get', 3], ['get', 1]])
Expected Output: [10, -1, 30, 10]
Explanation: After put(1,10),put(2,20): {1,2}. get(1)=10 makes 1 MRU. put(3,30) evicts LRU key 2 -> {1,3}. get(2)=-1 (evicted), get(3)=30, get(1)=10.
Input: (2, [['put', 1, 1], ['put', 2, 2], ['get', 1], ['put', 3, 3], ['get', 2], ['put', 4, 4], ['get', 1], ['get', 3], ['get', 4]])
Expected Output: [1, -1, -1, 3, 4]
Explanation: Classic LeetCode trace: get(1)=1; put(3) evicts 2 so get(2)=-1; put(4) evicts 1 so get(1)=-1; get(3)=3; get(4)=4.
Hints
- Combine a hash map (key -> node) with a doubly linked list ordered from least to most recently used. The map gives O(1) lookup; the list gives O(1) reordering and eviction.
- On get/put of an existing key, move that node to the most-recently-used end. On a brand-new put, append it and, if size exceeds capacity, remove the node at the least-recently-used end.
- An ordered hash map (Python OrderedDict / collections, Java LinkedHashMap, JS Map) gives the same behavior: move_to_end on access, popitem(last=False) to evict the oldest.