DSA · Design / Hash Table · #108
LRU Cache
Module 72 · difficulty 3/5·⏱ 30:00starts on first keystroke
Design a data structure that follows the constraints of a **Least Recently Used (LRU) cache**. Implement the `LRUCache` class: - `new LRUCache(capacity)` initializes the cache with a positive integer `capacity`. - `get(key)` returns the value of the `key` if it exists, otherwise returns `-1`. - `put(key, value)` updates the value of the `key` if it exists. Otherwise, adds the `key`-`value` pair. If inserting causes the number of keys to exceed `capacity`, **evict the least recently used key**. Both `get` and `put` must run in **O(1)** average time complexity. Any access (a successful `get` or any `put`) makes a key the most recently used.
Examples
["LRUCache","put","put","get","put","get","put","get","get","get"] [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]→[null,null,null,1,null,-1,null,-1,3,4]— Capacity 2. put(3,3) evicts key 2; put(4,4) evicts key 1.["LRUCache","put","get","put","get","get"] [[1],[2,1],[2],[3,2],[2],[3]]→[null,null,1,null,-1,2]— Capacity 1. put(3,2) evicts key 2, so get(2) returns -1.["LRUCache","put","put","get","put","get"] [[2],[1,1],[1,5],[1],[2,2],[1]]→[null,null,null,5,null,5]— Updating an existing key refreshes its value and recency.
Constraints
- · 1 <= capacity <= 3000
- · 0 <= key <= 10^4
- · 0 <= value <= 10^5
- · At most 2 * 10^5 calls will be made to get and put.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.