LRU Cache
Asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian, Salesforce
Problem
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement get and put operations in O(1) time. This is a classic system design and coding hybrid question.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Apple | Medium | View all Apple questions → |
| Netflix | Medium | View all Netflix questions → |
| Uber | Medium | View all Uber questions → |
| Atlassian | Medium | View all Atlassian questions → |
| Salesforce | Medium | View all Salesforce questions → |
How to Think About It
Two data structures needed: a hash map for O(1) key lookup, and a doubly linked list for O(1) insertion/deletion and maintaining access order.
The hash map stores key → node. The doubly linked list stores key-value pairs in access order: most recently used at the front, least recently used at the back.
On get or put: move the accessed node to the front of the list. This marks it as recently used.
On eviction (put when full): remove the node at the back of the list (least recently used). Also remove it from the hash map.
Dummy head and tail nodes simplify edge cases — you never need to check for null pointers during insertion/deletion.
Visual walkthrough for capacity=2:
put(1,1): list=[(1,1)], map={1:node1}
put(2,2): list=[(2,2),(1,1)], map={1:node1, 2:node2}
get(1): move node1 to front. list=[(1,1),(2,2)]. Return 1.
put(3,3): full! Remove back (2,2). list=[(3,3),(1,1)]. map={1:node1, 3:node3}
get(2): key 2 not in map. Return -1.
put(4,4): full! Remove back (1,1). list=[(4,4),(3,3)]. map={3:node3, 4:node4}
Optimal Approach
Data structures:
Hash map: key → node in doubly linked list- Doubly linked list: key-value pairs in access order (most recent at front)
get(key):
- If key not in map, return -1
- Move the node to front (mark as recently used)
- Return the value
put(key, value):
- If key exists: update value, move to front
- If key doesn't exist:
a. Create new node, add to front, add to map
b. If over capacity: remove back node from list AND map
Both operations are O(1) because:
Hash maplookup:O(1)- Doubly linked list insertion/deletion (given the node):
O(1)
What Trips People Up in Real Interviews
Not understanding the O(1) requirement for both get and put. A hash map alone gives O(1) get but O(n) eviction. A linked list alone gives O(1) eviction but O(n) lookup. You need both.
Confusing "least recently used" with "least frequently used." LRU evicts the item that was accessed longest ago, not the one accessed least often.
Forgetting to update access order on get. Every time you access an item (get or put), it becomes the most recently used. Move it to the tail of the linked list.
Not handling the case where the cache is full. When adding a new item and the cache is at capacity, evict the head of the linked list (least recently used) before adding.
Not storing the key in the linked list node. When evicting the LRU node, you need the key to remove it from the hash map. If the node only stores the value, you can't efficiently remove it.
Solution Code
class Node:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.map = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _add_front(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key in self.map:
node = self.map[key]
self._remove(node)
self._add_front(node)
return node.val
return -1
def put(self, key, value):
if key in self.map:
self._remove(self.map[key])
node = Node(key, value)
self._add_front(node)
self.map[key] = node
if len(self.map) > self.cap:
lru = self.tail.prev
self._remove(lru)
del self.map[lru.key]Frequently Asked Questions
What is the LRU Cache problem?
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement get and put operations in `O(1)` time. This is a classic system design and coding hybrid question.
How do you solve LRU Cache?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask LRU Cache?
LRU Cache is asked at Google, Meta, Amazon, Microsoft, Apple, Netflix, Uber, Atlassian, Salesforce. It is a medium difficulty problem.
What are common mistakes on LRU Cache?
- Not understanding the `O(1)` requirement for both get and put. A `hash map` alone gives `O(1)` get but `O(n)` eviction. A linked list alone gives `O(1)` eviction but `O(n)` lookup. You need both.
- Confusing "least recently used" with "least frequently used." LRU evicts the item that was accessed longest ago, not the one accessed least often.
- Forgetting to update access order on get. Every time you access an item (get or put), it becomes the most recently used. Move it to the tail of the linked list.
- Not handling the case where the cache is full. When adding a new item and the cache is at capacity, evict the head of the linked list (least recently used) before adding.
- Not storing the key in the linked list node. When evicting the LRU node, you need the key to remove it from the `hash map`. If the node only stores the value, you can't efficiently remove it.