146. LRU Cache
mediumDesign a cache that evicts the least-recently-used key when full, with O(1) get and put. The canonical hash-map plus doubly-linked list problem — drilled at every senior interview because the data-structure composition is the entire point.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity) initializes the LRU cache with positive size capacity. int get(int key) returns the value of the key if it exists, otherwise returns -1. void put(int key, int value) updates the value of the key if it exists. Otherwise, adds the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. The functions get and put must each run in O(1) average time complexity.
Constraints
1 <= capacity <= 30000 <= key <= 10^40 <= value <= 10^5At most 2 * 10^5 calls will be made to get and put.
Examples
Example 1
["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]Explanation: After putting (1,1) and (2,2) the cache is {1,2}. get(1) returns 1 and makes 1 most-recent. put(3,3) evicts 2 (the LRU). get(2) returns -1. put(4,4) evicts 1. get(1) is -1; get(3)=3; get(4)=4.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Two operations need O(1): look up by key, and move-to-front on touch. A hash map gives you O(1) lookup, a doubly-linked list gives you O(1) move.
Hint 2
Map each key to its node in the doubly-linked list. Maintain a head sentinel (most-recent end) and a tail sentinel (least-recent end).
Hint 3
On get: look up the node, unlink it, reinsert at head, return its value. On put: if the key exists, update value and move to head; otherwise insert a new node at head and, if size exceeds capacity, drop the node before tail and delete its key from the map.
Solution approach
Reveal approach
Hash map plus doubly-linked list with two sentinels. The list stores (key, value) nodes ordered by recency: head.next is most recent, tail.prev is least recent. The hash map maps key → node so look-ups are O(1). Use two sentinels (head and tail) so insertion and removal never need null checks. On get(key): if key not in map, return -1. Otherwise unlink the node (node.prev.next = node.next; node.next.prev = node.prev) and reinsert it right after head; return node.value. On put(key, value): if key is in the map, update value and move-to-head. Otherwise allocate a new node, insert after head, store node in map. If map.size > capacity, take lru = tail.prev, unlink it, and delete its key from the map. Storing the key on each node is what lets the eviction step also remove the right map entry in O(1). Total memory is O(capacity); both operations are O(1).
Complexity
- Time
- O(1)
- Space
- O(capacity)
Related patterns
- linked-list
- doubly-linked-list
- hash-map
- design
Related problems
- 460. LFU Cache
- 707. Design Linked List
- 432. All O`one Data Structure
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Meta
- Microsoft
- Apple
- Bloomberg
Practice these live with InterviewChamp.AI
Drill LRU Cache and Linked Lists problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →