Implement an LRU Cache
Company: Shopify
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem: LRU Cache (LeetCode 146)
Design and implement a **Least Recently Used (LRU) Cache** that supports the following operations in **average O(1) time**.
### Requirements
Implement a class `LRUCache` with:
- `LRUCache(int capacity)`: Initialize the cache with a **positive** capacity.
- `int get(int key)`: Return the value of the key if it exists; otherwise return `-1`.
- Accessing a key counts as using it, so it becomes **most recently used**.
- `void put(int key, int value)`: Insert or update the value of the key.
- If the key exists, update its value and mark it as **most recently used**.
- If inserting causes the cache to exceed capacity, **evict** the **least recently used** key.
### Notes / Constraints
- Keys and values are integers.
- Aim for **O(1)** average time per `get` and `put`.
- You may use any language, standard library containers, and write unit tests.
### Example
If `capacity = 2`:
1. `put(1, 1)` -> cache = {1=1}
2. `put(2, 2)` -> cache = {1=1, 2=2}
3. `get(1)` -> returns `1`, cache order becomes [2 (LRU), 1 (MRU)]
4. `put(3, 3)` -> evicts key `2`, cache = {1=1, 3=3}
5. `get(2)` -> returns `-1`
Quick Answer: This question evaluates competence in designing efficient cache mechanisms and mastery of data-structure strategies to support average O(1) get and put operations.
Design and implement a Least Recently Used (LRU) Cache supporting `get` and `put` in average O(1) time (LeetCode 146).
Implement a class `LRUCache`:
- `LRUCache(int capacity)` initializes the cache with a positive capacity.
- `int get(int key)` returns the value of the key if present, otherwise `-1`. Accessing a key marks it as most recently used.
- `void put(int key, int value)` inserts or updates a key. Updating marks it most recently used. If inserting exceeds capacity, evict the least recently used key.
### Harness encoding
Because this is a class-design problem, your solution is driven as a sequence of operations. Implement the function `solution(operations, arguments)`:
- `operations` is a list of method-name strings: `"LRUCache"` (the constructor, always first), `"get"`, or `"put"`.
- `arguments` is a parallel list of argument lists for each operation (`[capacity]` for the constructor, `[key]` for `get`, `[key, value]` for `put`).
- Return a list the same length as `operations`: the constructor and each `put` contribute `null` (`None` in Python); each `get` contributes its returned value.
### Example
For `capacity = 2`:
```
operations = ["LRUCache", "put", "put", "get", "put", "get"]
arguments = [[2], [1, 1], [2, 2], [1], [3, 3], [2]]
```
1. `put(1, 1)` -> cache {1=1}
2. `put(2, 2)` -> cache {1=1, 2=2}
3. `get(1)` -> returns 1, order becomes [2 (LRU), 1 (MRU)]
4. `put(3, 3)` -> evicts key 2, cache {1=1, 3=3}
5. `get(2)` -> returns -1
Return: `[null, null, null, 1, null, -1]`.
Constraints
- 1 <= capacity
- Keys and values are integers (LeetCode 146 uses 0 <= key, value <= 10^4 / 10^5).
- operations[0] is always "LRUCache" (the constructor).
- Each non-constructor operation is either "get" (args [key]) or "put" (args [key, value]).
- get and put must run in average O(1) time.
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: [None, None, None, 1, None, -1, None, -1, 3, 4]
Explanation: Canonical LeetCode 146 trace with capacity 2. get(1)=1 promotes key 1; put(3,3) evicts key 2 -> get(2)=-1; put(4,4) evicts key 1 -> get(1)=-1; key 3 and 4 remain -> get(3)=3, get(4)=4.
Input: (['LRUCache', 'put', 'put', 'get', 'put', 'get'], [[2], [1, 1], [2, 2], [1], [3, 3], [2]])
Expected Output: [None, None, None, 1, None, -1]
Explanation: The example from the prompt: get(1)=1 makes key 1 MRU, so put(3,3) evicts the now-least-recently-used key 2, giving get(2)=-1.
Hints
- Combine a hash map (key -> node) for O(1) lookup with a structure that maintains usage order so the least-recently-used entry is found in O(1).
- A doubly linked list with sentinel head/tail nodes lets you move a node to the front and pop from the back in O(1). Python's OrderedDict (move_to_end / popitem) and Java's LinkedHashMap in access-order mode encapsulate exactly this.
- On get: if the key is missing return -1; otherwise mark it most-recently-used before returning its value.
- On put: update or insert, mark it most-recently-used, then if size exceeds capacity evict the least-recently-used entry (the back of the list / first inserted ordered entry).