460. LFU Cache
Problem Description
This problem asks you to implement a Least Frequently Used (LFU) cache data structure with the following requirements:
What is an LFU Cache? An LFU cache evicts the least frequently used item when the cache reaches its capacity. Each item has a use counter that tracks how many times it has been accessed.
Required Operations:
-
LFUCache(int capacity)
: Initialize the cache with a given capacity. -
get(int key)
:- If the key exists in the cache, return its value
- If the key doesn't exist, return
-1
- When a key is accessed, its use counter increases by 1
-
put(int key, int value)
:- If the key already exists, update its value
- If the key doesn't exist, insert it into the cache
- When inserting a new key and the cache is at capacity, remove the least frequently used key first
- A newly inserted key starts with a use counter of 1
- Accessing a key (either updating or inserting) increases its use counter by 1
Tie-Breaking Rule: When multiple keys have the same frequency (use counter), the Least Recently Used (LRU) among them should be evicted. This means if two keys have been used the same number of times, remove the one that was accessed least recently.
Performance Requirement:
Both get
and put
operations must run in O(1)
average time complexity.
Example Scenario:
- If capacity is 2 and you insert keys A and B, both have frequency 1
- If you access A twice, A has frequency 3 and B has frequency 1
- When inserting a new key C at capacity, B gets evicted (lowest frequency)
- If both A and B had frequency 2, the one accessed least recently would be evicted
The challenge is designing a data structure that can track both frequency counts and recency of access while maintaining O(1)
operations for get, put, and eviction.
Intuition
To achieve O(1)
operations for an LFU cache, we need to efficiently track two things: frequency counts and the order of access within each frequency group.
The key insight is that we need a two-level organization:
- First level: Group nodes by their frequency
- Second level: Within each frequency group, maintain the order of access (for LRU tie-breaking)
Think of it like organizing books on shelves - each shelf represents a frequency level (1 time used, 2 times used, etc.), and books on each shelf are ordered by when they were last touched.
Why HashMap + Doubly Linked Lists?
For O(1)
access to any key, we need a HashMap that maps key -> Node
. But we also need to quickly find and remove the least frequently used item.
The challenge is that when we need to evict, we must:
- Find the minimum frequency group instantly
- Within that group, find the least recently used item instantly
- Remove that item in
O(1)
time
This leads us to use:
- A HashMap (
map
): Maps each key to its node forO(1)
lookup - Another HashMap (
freq_map
): Maps each frequency to a doubly linked list of nodes with that frequency - Doubly Linked Lists: For each frequency level, maintain nodes in LRU order (most recent at head, least recent at tail)
Why track min_freq
?
When the cache is full and we need to evict, we must quickly identify which frequency group has the lowest count. Instead of searching through all frequencies, we maintain a min_freq
variable that always points to the current minimum frequency level.
The frequency increment pattern:
When a node is accessed:
- Remove it from its current frequency list
- If that frequency list becomes empty and it was the minimum frequency, increment
min_freq
- Add the node to the
frequency + 1
list - Always add to the head of the new list (marking it as most recently used at that frequency)
This design ensures that at any moment, we can find the least frequently used (and least recently used in case of ties) item at the tail of the freq_map[min_freq]
list in O(1)
time.
Solution Approach
The implementation uses three main components: Node
, DoublyLinkedList
, and LFUCache
classes.
1. Node Class:
class Node:
def __init__(self, key: int, value: int):
self.key = key
self.value = value
self.freq = 1 # Initial frequency is 1
self.prev = None
self.next = None
Each node stores the key-value pair, its frequency count, and pointers for the doubly linked list.
2. DoublyLinkedList Class:
class DoublyLinkedList:
def __init__(self):
self.head = Node(-1, -1) # Dummy head
self.tail = Node(-1, -1) # Dummy tail
self.head.next = self.tail
self.tail.prev = self.head
Uses dummy head and tail nodes to simplify edge cases. This list maintains nodes in LRU order within each frequency level.
Key operations:
add_first(node)
: Adds a node right after the head (most recently used position)remove(node)
: Removes a node from the list inO(1)
timeremove_last()
: Removes the node before tail (least recently used)is_empty()
: Checks if the list contains any real nodes
3. LFUCache Class:
The cache maintains:
capacity
: Maximum number of itemsmin_freq
: Current minimum frequency in the cachemap
: HashMap mappingkey -> Node
freq_map
: HashMap mappingfrequency -> DoublyLinkedList
Get Operation:
def get(self, key: int) -> int:
if key not in self.map:
return -1
node = self.map[key]
self.incr_freq(node) # Increment frequency
return node.value
Put Operation:
def put(self, key: int, value: int) -> None:
if key in self.map:
# Update existing key
node = self.map[key]
node.value = value
self.incr_freq(node)
else:
# Insert new key
if len(self.map) == self.capacity:
# Evict LFU item
ls = self.freq_map[self.min_freq]
node = ls.remove_last() # Remove LRU from min frequency
self.map.pop(node.key)
# Create and add new node
node = Node(key, value)
self.add_node(node)
self.map[key] = node
self.min_freq = 1 # New node has frequency 1
Increment Frequency Helper:
def incr_freq(self, node: Node) -> None:
freq = node.freq
ls = self.freq_map[freq]
ls.remove(node) # Remove from current frequency list
if ls.is_empty():
self.freq_map.pop(freq) # Clean up empty frequency
if freq == self.min_freq:
self.min_freq += 1 # Update min_freq if needed
node.freq += 1
self.add_node(node) # Add to new frequency list
Add Node Helper:
def add_node(self, node: Node) -> None:
freq = node.freq
ls = self.freq_map[freq] # Get or create list for this frequency
ls.add_first(node) # Add as most recently used
self.freq_map[freq] = ls
Time Complexity:
get
:O(1)
- HashMap lookup + list operationsput
:O(1)
- HashMap operations + list operations- Space:
O(capacity)
for storing the cache items
The solution elegantly handles the LFU eviction policy with LRU tie-breaking by maintaining a two-level structure where frequencies map to ordered lists, ensuring all operations remain O(1)
.
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a concrete example with capacity 2 to see how the LFU cache operates:
Initial State:
- Cache capacity: 2
- Cache is empty
min_freq = 0
Step 1: put(1, 10)
- Cache is not full, create new node with key=1, value=10, freq=1
- Add node to frequency 1's linked list
- Update
min_freq = 1
- State:
map: {1: Node(1,10,freq=1)} freq_map: {1: [Node(1,10)]} min_freq: 1
Step 2: put(2, 20)
- Cache is not full, create new node with key=2, value=20, freq=1
- Add node to frequency 1's linked list (at head, so it's most recent)
- State:
map: {1: Node(1,10,freq=1), 2: Node(2,20,freq=1)} freq_map: {1: [Node(2,20) -> Node(1,10)]} // 2 is more recent min_freq: 1
Step 3: get(1)
- Find node with key=1 in map
- Increment its frequency from 1 to 2:
- Remove Node(1,10) from frequency 1's list
- Frequency 1's list now only has Node(2,20)
- Add Node(1,10) to frequency 2's list
- Return value 10
- State:
map: {1: Node(1,10,freq=2), 2: Node(2,20,freq=1)} freq_map: {1: [Node(2,20)], 2: [Node(1,10)]} min_freq: 1 // Still 1 because freq_map[1] is not empty
Step 4: put(3, 30)
- Cache is full (size = 2), need to evict
- Look at
freq_map[min_freq]
which isfreq_map[1]
containing [Node(2,20)] - Remove the least recently used from minimum frequency (Node(2,20))
- Remove key=2 from map
- Add new Node(3,30) with freq=1
- Update
min_freq = 1
- State:
map: {1: Node(1,10,freq=2), 3: Node(3,30,freq=1)} freq_map: {1: [Node(3,30)], 2: [Node(1,10)]} min_freq: 1
Step 5: get(3)
- Find node with key=3 in map
- Increment its frequency from 1 to 2:
- Remove Node(3,30) from frequency 1's list
- Frequency 1's list becomes empty, so remove it from freq_map
- Since freq=1 was min_freq and now empty, increment
min_freq = 2
- Add Node(3,30) to frequency 2's list (at head)
- Return value 30
- State:
map: {1: Node(1,10,freq=2), 3: Node(3,30,freq=2)} freq_map: {2: [Node(3,30) -> Node(1,10)]} // 3 is more recent min_freq: 2
Step 6: put(4, 40)
- Cache is full, need to evict
- Look at
freq_map[min_freq]
which isfreq_map[2]
containing [Node(3,30) -> Node(1,10)] - Remove the least recently used from minimum frequency (tail = Node(1,10))
- Remove key=1 from map
- Add new Node(4,40) with freq=1
- Update
min_freq = 1
(new node always has frequency 1) - State:
map: {3: Node(3,30,freq=2), 4: Node(4,40,freq=1)} freq_map: {1: [Node(4,40)], 2: [Node(3,30)]} min_freq: 1
This example demonstrates:
- How nodes move between frequency lists when accessed
- How LRU ordering within each frequency list handles tie-breaking
- How
min_freq
tracks the lowest frequency for efficient eviction - How the data structure maintains O(1) operations throughout
Solution Implementation
1from collections import defaultdict
2from typing import Optional
3
4
5class Node:
6 """Node for doubly linked list to store cache entries."""
7
8 def __init__(self, key: int, value: int) -> None:
9 self.key = key
10 self.value = value
11 self.freq = 1 # Frequency counter starts at 1
12 self.prev: Optional[Node] = None
13 self.next: Optional[Node] = None
14
15
16class DoublyLinkedList:
17 """Doubly linked list to maintain nodes with same frequency in LRU order."""
18
19 def __init__(self) -> None:
20 # Create dummy head and tail nodes for easier manipulation
21 self.head = Node(-1, -1)
22 self.tail = Node(-1, -1)
23 self.head.next = self.tail
24 self.tail.prev = self.head
25
26 def add_first(self, node: Node) -> None:
27 """Add node right after head (most recently used position)."""
28 node.prev = self.head
29 node.next = self.head.next
30 self.head.next.prev = node
31 self.head.next = node
32
33 def remove(self, node: Node) -> Node:
34 """Remove a specific node from the list."""
35 node.next.prev = node.prev
36 node.prev.next = node.next
37 node.next = None
38 node.prev = None
39 return node
40
41 def remove_last(self) -> Node:
42 """Remove and return the least recently used node (before tail)."""
43 return self.remove(self.tail.prev)
44
45 def is_empty(self) -> bool:
46 """Check if the list is empty (only contains dummy nodes)."""
47 return self.head.next == self.tail
48
49
50class LFUCache:
51 """
52 Least Frequently Used (LFU) cache implementation.
53 Evicts least frequently used items when capacity is reached.
54 For items with same frequency, evicts least recently used.
55 """
56
57 def __init__(self, capacity: int) -> None:
58 self.capacity = capacity
59 self.min_freq = 0 # Track minimum frequency for eviction
60 self.node_map: dict[int, Node] = {} # Map from key to node
61 self.freq_map: defaultdict[int, DoublyLinkedList] = defaultdict(DoublyLinkedList) # Map from frequency to list of nodes
62
63 def get(self, key: int) -> int:
64 """
65 Get value for the given key.
66 Returns -1 if key doesn't exist.
67 """
68 # Handle edge cases
69 if self.capacity == 0 or key not in self.node_map:
70 return -1
71
72 # Get node and update its frequency
73 node = self.node_map[key]
74 self._increment_frequency(node)
75 return node.value
76
77 def put(self, key: int, value: int) -> None:
78 """
79 Insert or update key-value pair in cache.
80 Evicts LFU item if cache is at capacity.
81 """
82 # Handle zero capacity
83 if self.capacity == 0:
84 return
85
86 # Update existing key
87 if key in self.node_map:
88 node = self.node_map[key]
89 node.value = value
90 self._increment_frequency(node)
91 return
92
93 # Evict LFU item if at capacity
94 if len(self.node_map) == self.capacity:
95 freq_list = self.freq_map[self.min_freq]
96 evicted_node = freq_list.remove_last()
97 del self.node_map[evicted_node.key]
98
99 # Add new node
100 node = Node(key, value)
101 self._add_node(node)
102 self.node_map[key] = node
103 self.min_freq = 1 # New node has frequency 1
104
105 def _increment_frequency(self, node: Node) -> None:
106 """
107 Increment frequency of a node and move it to appropriate frequency list.
108 """
109 freq = node.freq
110 freq_list = self.freq_map[freq]
111
112 # Remove node from current frequency list
113 freq_list.remove(node)
114
115 # Clean up empty frequency list and update min_freq if needed
116 if freq_list.is_empty():
117 del self.freq_map[freq]
118 if freq == self.min_freq:
119 self.min_freq += 1
120
121 # Increment frequency and add to new frequency list
122 node.freq += 1
123 self._add_node(node)
124
125 def _add_node(self, node: Node) -> None:
126 """
127 Add node to the frequency list corresponding to its frequency.
128 """
129 freq = node.freq
130 freq_list = self.freq_map[freq]
131 freq_list.add_first(node)
132
133
134# Your LFUCache object will be instantiated and called as such:
135# obj = LFUCache(capacity)
136# param_1 = obj.get(key)
137# obj.put(key, value)
138
1class LFUCache {
2 // Map to store key-node pairs for O(1) access
3 private final Map<Integer, Node> cache;
4 // Map to store frequency-list pairs, where each list contains nodes with same frequency
5 private final Map<Integer, DoublyLinkedList> frequencyMap;
6 // Maximum capacity of the cache
7 private final int capacity;
8 // Track the minimum frequency in the cache for eviction
9 private int minFrequency;
10
11 /**
12 * Initialize the LFU cache with given capacity
13 * @param capacity Maximum number of key-value pairs the cache can hold
14 */
15 public LFUCache(int capacity) {
16 this.capacity = capacity;
17 this.cache = new HashMap<>(capacity, 1);
18 this.frequencyMap = new HashMap<>();
19 this.minFrequency = 0;
20 }
21
22 /**
23 * Get the value of the key if it exists in the cache
24 * @param key The key to look up
25 * @return The value associated with the key, or -1 if key doesn't exist
26 */
27 public int get(int key) {
28 // Handle edge case of zero capacity
29 if (capacity == 0) {
30 return -1;
31 }
32
33 // Key not found in cache
34 if (!cache.containsKey(key)) {
35 return -1;
36 }
37
38 // Key exists - update frequency and return value
39 Node node = cache.get(key);
40 incrementFrequency(node);
41 return node.value;
42 }
43
44 /**
45 * Update the value of the key if present, otherwise insert the key-value pair
46 * @param key The key to insert or update
47 * @param value The value to associate with the key
48 */
49 public void put(int key, int value) {
50 // Handle edge case of zero capacity
51 if (capacity == 0) {
52 return;
53 }
54
55 // Update existing key
56 if (cache.containsKey(key)) {
57 Node node = cache.get(key);
58 node.value = value;
59 incrementFrequency(node);
60 return;
61 }
62
63 // Remove least frequently used item if cache is full
64 if (cache.size() == capacity) {
65 DoublyLinkedList minFrequencyList = frequencyMap.get(minFrequency);
66 Node nodeToRemove = minFrequencyList.removeLast();
67 cache.remove(nodeToRemove.key);
68 }
69
70 // Add new node to cache
71 Node newNode = new Node(key, value);
72 addNodeToFrequencyMap(newNode);
73 cache.put(key, newNode);
74 minFrequency = 1; // New node always has frequency 1
75 }
76
77 /**
78 * Increment the frequency of a node and move it to appropriate frequency list
79 * @param node The node whose frequency needs to be incremented
80 */
81 private void incrementFrequency(Node node) {
82 int currentFrequency = node.frequency;
83
84 // Remove node from current frequency list
85 DoublyLinkedList currentList = frequencyMap.get(currentFrequency);
86 currentList.remove(node);
87
88 // Clean up empty frequency list and update minFrequency if needed
89 if (currentList.isEmpty()) {
90 frequencyMap.remove(currentFrequency);
91 if (currentFrequency == minFrequency) {
92 minFrequency++;
93 }
94 }
95
96 // Increment frequency and add to new frequency list
97 node.frequency++;
98 addNodeToFrequencyMap(node);
99 }
100
101 /**
102 * Add a node to the frequency map based on its current frequency
103 * @param node The node to add to frequency map
104 */
105 private void addNodeToFrequencyMap(Node node) {
106 int frequency = node.frequency;
107
108 // Get or create the list for this frequency
109 DoublyLinkedList list = frequencyMap.computeIfAbsent(frequency,
110 k -> new DoublyLinkedList());
111
112 // Add node to the front of the list (most recently used)
113 list.addFirst(node);
114 }
115
116 /**
117 * Node class representing a cache entry
118 */
119 private static class Node {
120 int key;
121 int value;
122 int frequency;
123 Node prev;
124 Node next;
125
126 Node(int key, int value) {
127 this.key = key;
128 this.value = value;
129 this.frequency = 1; // Initial frequency is always 1
130 }
131 }
132
133 /**
134 * Doubly linked list to maintain LRU order within same frequency
135 */
136 private static class DoublyLinkedList {
137 // Dummy head and tail nodes to simplify operations
138 private final Node head;
139 private final Node tail;
140
141 public DoublyLinkedList() {
142 // Initialize dummy nodes
143 head = new Node(-1, -1);
144 tail = new Node(-1, -1);
145 head.next = tail;
146 tail.prev = head;
147 }
148
149 /**
150 * Add a node to the front of the list (most recently used position)
151 * @param node The node to add
152 */
153 public void addFirst(Node node) {
154 node.prev = head;
155 node.next = head.next;
156 head.next.prev = node;
157 head.next = node;
158 }
159
160 /**
161 * Remove a specific node from the list
162 * @param node The node to remove
163 * @return The removed node
164 */
165 public Node remove(Node node) {
166 node.next.prev = node.prev;
167 node.prev.next = node.next;
168 node.next = null;
169 node.prev = null;
170 return node;
171 }
172
173 /**
174 * Remove the last node from the list (least recently used)
175 * @return The removed node
176 */
177 public Node removeLast() {
178 return remove(tail.prev);
179 }
180
181 /**
182 * Check if the list is empty
183 * @return true if list is empty, false otherwise
184 */
185 public boolean isEmpty() {
186 return head.next == tail;
187 }
188 }
189}
190
1class Node {
2public:
3 int key;
4 int value;
5 int freq;
6 Node* prev;
7 Node* next;
8
9 // Constructor to initialize a node with key-value pair and frequency 1
10 Node(int key, int value) {
11 this->key = key;
12 this->value = value;
13 this->freq = 1;
14 this->prev = nullptr;
15 this->next = nullptr;
16 }
17};
18
19class DoublyLinkedList {
20public:
21 Node* head; // Dummy head node
22 Node* tail; // Dummy tail node
23
24 // Initialize doubly linked list with dummy head and tail
25 DoublyLinkedList() {
26 this->head = new Node(-1, -1);
27 this->tail = new Node(-1, -1);
28 this->head->next = this->tail;
29 this->tail->prev = this->head;
30 }
31
32 // Add a node right after the dummy head (most recently used position)
33 void addFirst(Node* node) {
34 node->prev = this->head;
35 node->next = this->head->next;
36 this->head->next->prev = node;
37 this->head->next = node;
38 }
39
40 // Remove a specific node from the list and return it
41 Node* remove(Node* node) {
42 node->next->prev = node->prev;
43 node->prev->next = node->next;
44 node->next = nullptr;
45 node->prev = nullptr;
46 return node;
47 }
48
49 // Remove and return the least recently used node (node before dummy tail)
50 Node* removeLast() {
51 return remove(this->tail->prev);
52 }
53
54 // Check if the list is empty (only contains dummy nodes)
55 bool isEmpty() {
56 return this->head->next == this->tail;
57 }
58};
59
60class LFUCache {
61public:
62 // Initialize LFU cache with given capacity
63 LFUCache(int capacity) {
64 this->capacity = capacity;
65 this->minFreq = 0;
66 }
67
68 // Get value for the given key, return -1 if key doesn't exist
69 int get(int key) {
70 // Handle edge case: zero capacity or key not found
71 if (capacity == 0 || keyToNodeMap.find(key) == keyToNodeMap.end()) {
72 return -1;
73 }
74
75 // Get the node and increment its frequency
76 Node* node = keyToNodeMap[key];
77 incrementFrequency(node);
78 return node->value;
79 }
80
81 // Put key-value pair into cache
82 void put(int key, int value) {
83 // Edge case: zero capacity cache
84 if (capacity == 0) {
85 return;
86 }
87
88 // If key exists, update its value and increment frequency
89 if (keyToNodeMap.find(key) != keyToNodeMap.end()) {
90 Node* node = keyToNodeMap[key];
91 node->value = value;
92 incrementFrequency(node);
93 return;
94 }
95
96 // If cache is full, evict the least frequently used item
97 if (keyToNodeMap.size() == capacity) {
98 DoublyLinkedList* minFreqList = frequencyToListMap[minFreq];
99 Node* nodeToEvict = minFreqList->removeLast();
100 keyToNodeMap.erase(nodeToEvict->key);
101 delete nodeToEvict; // Free memory
102 }
103
104 // Create new node and add it to the cache
105 Node* newNode = new Node(key, value);
106 addNodeToFrequencyList(newNode);
107 keyToNodeMap[key] = newNode;
108 minFreq = 1; // New node always has frequency 1
109 }
110
111private:
112 int capacity; // Maximum cache capacity
113 int minFreq; // Current minimum frequency in cache
114 unordered_map<int, Node*> keyToNodeMap; // Map from key to node pointer
115 unordered_map<int, DoublyLinkedList*> frequencyToListMap; // Map from frequency to list of nodes
116
117 // Increment the frequency of a node and move it to appropriate frequency list
118 void incrementFrequency(Node* node) {
119 int currentFreq = node->freq;
120 DoublyLinkedList* currentList = frequencyToListMap[currentFreq];
121
122 // Remove node from current frequency list
123 currentList->remove(node);
124
125 // If current frequency list becomes empty, clean up
126 if (currentList->isEmpty()) {
127 frequencyToListMap.erase(currentFreq);
128 // Update minFreq if necessary
129 if (currentFreq == minFreq) {
130 minFreq++;
131 }
132 }
133
134 // Increment frequency and add to new frequency list
135 node->freq++;
136 addNodeToFrequencyList(node);
137 }
138
139 // Add a node to its corresponding frequency list
140 void addNodeToFrequencyList(Node* node) {
141 int freq = node->freq;
142
143 // Create new frequency list if it doesn't exist
144 if (frequencyToListMap.find(freq) == frequencyToListMap.end()) {
145 frequencyToListMap[freq] = new DoublyLinkedList();
146 }
147
148 // Add node to the front of the frequency list (most recently used)
149 DoublyLinkedList* freqList = frequencyToListMap[freq];
150 freqList->addFirst(node);
151 }
152};
153
154/**
155 * Your LFUCache object will be instantiated and called as such:
156 * LFUCache* obj = new LFUCache(capacity);
157 * int param_1 = obj->get(key);
158 * obj->put(key,value);
159 */
160
1// Node structure for LFU Cache
2interface Node {
3 key: number;
4 value: number;
5 freq: number;
6 prev: Node | null;
7 next: Node | null;
8}
9
10// Create a new node with key-value pair and frequency 1
11function createNode(key: number, value: number): Node {
12 return {
13 key: key,
14 value: value,
15 freq: 1,
16 prev: null,
17 next: null
18 };
19}
20
21// Doubly linked list structure
22interface DoublyLinkedList {
23 head: Node;
24 tail: Node;
25}
26
27// Initialize doubly linked list with dummy head and tail
28function createDoublyLinkedList(): DoublyLinkedList {
29 const head = createNode(-1, -1);
30 const tail = createNode(-1, -1);
31 head.next = tail;
32 tail.prev = head;
33 return { head, tail };
34}
35
36// Add a node right after the dummy head (most recently used position)
37function addFirst(list: DoublyLinkedList, node: Node): void {
38 node.prev = list.head;
39 node.next = list.head.next;
40 if (list.head.next) {
41 list.head.next.prev = node;
42 }
43 list.head.next = node;
44}
45
46// Remove a specific node from the list and return it
47function removeNode(node: Node): Node {
48 if (node.prev) {
49 node.prev.next = node.next;
50 }
51 if (node.next) {
52 node.next.prev = node.prev;
53 }
54 node.next = null;
55 node.prev = null;
56 return node;
57}
58
59// Remove and return the least recently used node (node before dummy tail)
60function removeLast(list: DoublyLinkedList): Node | null {
61 if (list.tail.prev && list.tail.prev !== list.head) {
62 return removeNode(list.tail.prev);
63 }
64 return null;
65}
66
67// Check if the list is empty (only contains dummy nodes)
68function isEmpty(list: DoublyLinkedList): boolean {
69 return list.head.next === list.tail;
70}
71
72// Global variables for LFU Cache
73let capacity: number = 0;
74let minFreq: number = 0;
75let keyToNodeMap: Map<number, Node> = new Map();
76let frequencyToListMap: Map<number, DoublyLinkedList> = new Map();
77
78// Initialize LFU cache with given capacity
79function LFUCache(cap: number): void {
80 capacity = cap;
81 minFreq = 0;
82 keyToNodeMap = new Map();
83 frequencyToListMap = new Map();
84}
85
86// Add a node to its corresponding frequency list
87function addNodeToFrequencyList(node: Node): void {
88 const freq = node.freq;
89
90 // Create new frequency list if it doesn't exist
91 if (!frequencyToListMap.has(freq)) {
92 frequencyToListMap.set(freq, createDoublyLinkedList());
93 }
94
95 // Add node to the front of the frequency list (most recently used)
96 const freqList = frequencyToListMap.get(freq)!;
97 addFirst(freqList, node);
98}
99
100// Increment the frequency of a node and move it to appropriate frequency list
101function incrementFrequency(node: Node): void {
102 const currentFreq = node.freq;
103 const currentList = frequencyToListMap.get(currentFreq);
104
105 if (!currentList) return;
106
107 // Remove node from current frequency list
108 removeNode(node);
109
110 // If current frequency list becomes empty, clean up
111 if (isEmpty(currentList)) {
112 frequencyToListMap.delete(currentFreq);
113 // Update minFreq if necessary
114 if (currentFreq === minFreq) {
115 minFreq++;
116 }
117 }
118
119 // Increment frequency and add to new frequency list
120 node.freq++;
121 addNodeToFrequencyList(node);
122}
123
124// Get value for the given key, return -1 if key doesn't exist
125function get(key: number): number {
126 // Handle edge case: zero capacity or key not found
127 if (capacity === 0 || !keyToNodeMap.has(key)) {
128 return -1;
129 }
130
131 // Get the node and increment its frequency
132 const node = keyToNodeMap.get(key)!;
133 incrementFrequency(node);
134 return node.value;
135}
136
137// Put key-value pair into cache
138function put(key: number, value: number): void {
139 // Edge case: zero capacity cache
140 if (capacity === 0) {
141 return;
142 }
143
144 // If key exists, update its value and increment frequency
145 if (keyToNodeMap.has(key)) {
146 const node = keyToNodeMap.get(key)!;
147 node.value = value;
148 incrementFrequency(node);
149 return;
150 }
151
152 // If cache is full, evict the least frequently used item
153 if (keyToNodeMap.size === capacity) {
154 const minFreqList = frequencyToListMap.get(minFreq);
155 if (minFreqList) {
156 const nodeToEvict = removeLast(minFreqList);
157 if (nodeToEvict) {
158 keyToNodeMap.delete(nodeToEvict.key);
159 }
160 }
161 }
162
163 // Create new node and add it to the cache
164 const newNode = createNode(key, value);
165 addNodeToFrequencyList(newNode);
166 keyToNodeMap.set(key, newNode);
167 minFreq = 1; // New node always has frequency 1
168}
169
Time and Space Complexity
Time Complexity:
-
get(key)
:O(1)
- Checking if key exists in map:
O(1)
(hash map lookup) - Calling
incr_freq()
:O(1)
(involves removing and adding node to doubly linked list) - Return value:
O(1)
- Checking if key exists in map:
-
put(key, value)
:O(1)
- Checking if key exists in map:
O(1)
(hash map lookup) - If key exists, update value and call
incr_freq()
:O(1)
- If at capacity, remove LFU node:
O(1)
(remove from tail of min_freq list) - Create new node and call
add_node()
:O(1)
- Update map and min_freq:
O(1)
- Checking if key exists in map:
-
Helper functions:
incr_freq()
:O(1)
- removes node from current frequency list, updates frequency, adds to new frequency listadd_node()
:O(1)
- adds node to head of frequency listadd_first()
:O(1)
- pointer manipulation in doubly linked listremove()
:O(1)
- pointer manipulation in doubly linked listremove_last()
:O(1)
- calls remove on tail's previous nodeis_empty()
:O(1)
- simple comparison
Space Complexity: O(capacity)
self.map
:O(n)
wheren ≤ capacity
(stores at most capacity nodes)self.freq_map
:O(n)
in worst case (each node could have different frequency)- Each
Node
:O(1)
space, totalO(n)
for all nodes - Each
DoublyLinkedList
:O(1)
overhead (just head and tail sentinels), but contains nodes already counted - Total:
O(capacity)
since the cache never stores more than capacity items
Common Pitfalls
1. Forgetting to Handle Zero Capacity Edge Case
One of the most common pitfalls is not properly handling when the cache is initialized with capacity 0. This can lead to unexpected behavior or errors when trying to perform operations.
Problem Code:
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
# ... other initialization
def put(self, key: int, value: int) -> None:
# Missing zero capacity check
if key in self.node_map:
# update logic
else:
if len(self.node_map) == self.capacity: # This will evict when capacity=0!
# eviction logic
# add new node
Solution:
Always check for zero capacity at the beginning of both get
and put
methods:
def get(self, key: int) -> int:
if self.capacity == 0: # Handle zero capacity
return -1
# ... rest of logic
def put(self, key: int, value: int) -> None:
if self.capacity == 0: # Handle zero capacity
return
# ... rest of logic
2. Incorrectly Updating min_freq When Removing Nodes
A critical pitfall is not properly maintaining the min_freq
variable when removing nodes from frequency lists, especially when the minimum frequency list becomes empty.
Problem Code:
def _increment_frequency(self, node: Node) -> None:
freq = node.freq
freq_list = self.freq_map[freq]
freq_list.remove(node)
# Forgot to update min_freq when the list becomes empty!
if freq_list.is_empty():
del self.freq_map[freq]
# Missing: if freq == self.min_freq: self.min_freq += 1
node.freq += 1
self._add_node(node)
Solution:
Always update min_freq
when the minimum frequency list becomes empty:
if freq_list.is_empty(): del self.freq_map[freq] if freq == self.min_freq: self.min_freq += 1 # Critical update!
3. Not Resetting min_freq When Adding New Nodes
When adding a new node to the cache, forgetting to reset min_freq
to 1 can cause incorrect eviction behavior.
Problem Code:
def put(self, key: int, value: int) -> None:
if key not in self.node_map:
# eviction logic if needed
node = Node(key, value)
self._add_node(node)
self.node_map[key] = node
# Forgot to set: self.min_freq = 1
Solution:
Always set min_freq = 1
when adding a new node:
node = Node(key, value) self._add_node(node) self.node_map[key] = node self.min_freq = 1 # New nodes always have frequency 1
4. Memory Leak from Not Properly Cleaning Up Node Pointers
When removing nodes from the doubly linked list, failing to set the prev
and next
pointers to None
can cause memory leaks.
Problem Code:
def remove(self, node: Node) -> Node:
node.next.prev = node.prev
node.prev.next = node.next
# Forgot to clean up node's pointers!
return node
Solution: Always clean up the removed node's pointers:
def remove(self, node: Node) -> Node:
node.next.prev = node.prev
node.prev.next = node.next
node.next = None # Clean up
node.prev = None # Clean up
return node
5. Using Regular Dict Instead of defaultdict
Using a regular dictionary for freq_map
requires extra code to check and create new lists for each frequency.
Problem Code:
self.freq_map: dict[int, DoublyLinkedList] = {}
def _add_node(self, node: Node) -> None:
freq = node.freq
if freq not in self.freq_map: # Extra check needed
self.freq_map[freq] = DoublyLinkedList()
freq_list = self.freq_map[freq]
freq_list.add_first(node)
Solution:
Use defaultdict
to automatically create new lists:
from collections import defaultdict
self.freq_map: defaultdict[int, DoublyLinkedList] = defaultdict(DoublyLinkedList)
def _add_node(self, node: Node) -> None:
freq = node.freq
freq_list = self.freq_map[freq] # Automatically creates new list if needed
freq_list.add_first(node)
These pitfalls can cause subtle bugs that are difficult to debug, especially under edge cases. Careful attention to state management and edge case handling is crucial for a correct LFU cache implementation.
How does quick sort divide the problem into subproblems?
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!