460. LFU Cache
Asked at Apple, Ripple, Salesforce, Walmart and 1 more
Difficulty
Hard
Time
O(1) average per get and per put
Space
O(capacity)
Pattern
Hash Table
Companies
5
Problem
Design a Least Frequently Used (LFU) cache. The cache has a fixed capacity. Each key in the cache has a use counter: how many times it has been read or written.
Implement a class LFUCache with two methods. get(key) returns the stored value, or -1 if the key is not in the cache. put(key, value) inserts a new key or updates an existing one.
When put needs to add a key and the cache is already full, one key must be removed first. Remove the key with the smallest use counter. If several keys share that smallest counter, remove the one that was used least recently (the tie-breaker is LRU).
A key starts with counter 1 when it is first inserted. Every get or put on a key that is already in the cache increases its counter by one. Both methods must run in O(1) average time.
Eviction rule: lowest counter, then oldest
Constraints
- ●
1 <= capacity <= 10^4 - ●
0 <= key <= 10^5 - ●
0 <= value <= 10^9 - ●
At most 2 * 10^5 calls will be made to get and put
Examples
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]][null, null, null, 1, null, -1, 3, null, -1, 3, 4]Asked At
5 companies| Company | Difficulty | |
|---|---|---|
| Apple | Hard | View all Apple questions → |
| Ripple | Hard | View all Ripple questions → |
| Salesforce | Hard | View all Salesforce questions → |
| Walmart | Hard | View all Walmart questions → |
| Goldman Sachs | Hard | View all Goldman Sachs questions → |
How to Think About It
Three data structures: (1) hash map key -> node, (2) hash map frequency -> doubly linked list of nodes, (3) variable minFreq tracking the current minimum frequency.
Each node stores key, value, frequency, prev, and next pointers. The doubly linked list per frequency maintains insertion order (most recent at tail, least recent at head).
On get(key): if key exists, remove from current frequency list, increment frequency, add to new frequency list. Update minFreq if the old list became empty.
On put(key, value): if key exists, update value and frequency (same as get). If at capacity, remove head of minFreq list (least recently used among least frequently used). Add new node to freq=1 list.
Why O(1): hash map lookups are O(1), doubly linked list insert/delete at known nodes is O(1).
Optimal Approach
Data structures:
keyToNode: key -> Node (forO(1)lookup)freqToList: frequency -> doubly linked list (forO(1)eviction)minFreq: current minimum frequency
get(key):
- If key not in
keyToNode, return -1. - Remove node from current frequency list.
- Increment node frequency.
- Add node to new frequency list.
- If old frequency list is empty and it was
minFreq, incrementminFreq. - Return node value.
put(key, value):
- If key exists: update value, call get (triggers frequency update).
- If key does not exist:
a. If at capacity: remove head ofminFreqlist, delete fromkeyToNode.
b. Create new node with freq=1, add to freq=1 list, add tokeyToNode.
c. SetminFreq = 1.
Time: O(1) for both operations. Space: O(capacity).
Buckets by frequency plus a minFreq pointer
What Trips People Up in Real Interviews
Confusing LFU with LRU. LFU evicts the least frequently used item. On ties, it evicts the least recently used among the tied items. Both frequency and recency matter.
Not maintaining a separate doubly linked list per frequency. Without per-frequency lists, you cannot achieve O(1) eviction of the least recently used item within a frequency tier.
Forgetting to update minFreq when a frequency list becomes empty. If the list at minFreq is emptied after a get/put, minFreq must increment to the next occupied frequency.
Not storing the key in the node. When evicting from a frequency list, you need the key to remove the entry from keyToNode. Without it, the hash map entry leaks.
Evicting the most recently used item instead of the least recently used within a frequency tier. The doubly linked list must maintain insertion order so the head is always the LRU item for that frequency.
Solution Code
O(1) average per get and per put timeclass Node:
def __init__(self, key=0, val=0, freq=1):
self.key = key
self.val = val
self.freq = freq
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0
def add(self, node):
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
self.size += 1
def remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
self.size -= 1
def popFront(self):
if self.size == 0:
return None
node = self.head.next
self.remove(node)
return node
class LFUCache:
def __init__(self, capacity):
self.cap = capacity
self.keyToNode = {}
self.freqToList = {}
self.minFreq = 0
def _removeFreq(self, freq):
if freq in self.freqToList and self.freqToList[freq].size == 0:
del self.freqToList[freq]
def get(self, key):
if key not in self.keyToNode:
return -1
node = self.keyToNode[key]
self.freqToList[node.freq].remove(node)
if self.freqToList[node.freq].size == 0:
del self.freqToList[node.freq]
if self.minFreq == node.freq:
self.minFreq += 1
node.freq += 1
if node.freq not in self.freqToList:
self.freqToList[node.freq] = DoublyLinkedList()
self.freqToList[node.freq].add(node)
return node.val
def put(self, key, value):
if self.cap == 0:
return
if key in self.keyToNode:
node = self.keyToNode[key]
node.val = value
self.freqToList[node.freq].remove(node)
if self.freqToList[node.freq].size == 0:
del self.freqToList[node.freq]
if self.minFreq == node.freq:
self.minFreq += 1
node.freq += 1
if node.freq not in self.freqToList:
self.freqToList[node.freq] = DoublyLinkedList()
self.freqToList[node.freq].add(node)
return
if len(self.keyToNode) >= self.cap:
evict = self.freqToList[self.minFreq].popFront()
del self.keyToNode[evict.key]
self._removeFreq(self.minFreq)
newNode = Node(key, value, 1)
self.keyToNode[key] = newNode
if 1 not in self.freqToList:
self.freqToList[1] = DoublyLinkedList()
self.freqToList[1].add(newNode)
self.minFreq = 1Frequently Asked Questions
What is the LFU Cache problem?
Design and implement a data structure for a Least Frequently Used (LFU) cache. Implement get and put operations in `O(1)` time. When the cache reaches capacity, the least frequently used item is evicted. If there is a tie, the least recently used item is evicted.
How do you solve LFU Cache?
The optimal approach runs in O(1) average per get and per put time and O(capacity) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask LFU Cache?
LFU Cache is asked at Apple, Ripple, Salesforce, Walmart, Goldman Sachs. It is a hard difficulty problem.
What are common mistakes on LFU Cache?
- Confusing LFU with LRU. LFU evicts the least frequently used item. On ties, it evicts the least recently used among the tied items. Both frequency and recency matter.
- Not maintaining a separate doubly linked list per frequency. Without per-frequency lists, you cannot achieve `O(1)` eviction of the least recently used item within a frequency tier.
- Forgetting to update `minFreq` when a frequency list becomes empty. If the list at `minFreq` is emptied after a get/put, `minFreq` must increment to the next occupied frequency.
- Not storing the key in the node. When evicting from a frequency list, you need the key to remove the entry from `keyToNode`. Without it, the hash map entry leaks.
- Evicting the most recently used item instead of the least recently used within a frequency tier. The doubly linked list must maintain insertion order so the head is always the LRU item for that frequency.