Design and implement a data structure for a Least Frequently Used (LFU) cache.
Implement the LFUCache class:
LFUCache(int capacity) Initializes the object with the capacity of the data structure.int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.
When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.
The functions get and put must each run in O(1) average time complexity.
Example 1:
Input
["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]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
Explanation
// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1); // cache=[1,_], cnt(1)=1
lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1); // return 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4); // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4); // return 4
// cache=[4,3], cnt(4)=2, cnt(3)=3
Constraints:
1 <= capacity <= 1040 <= key <= 1050 <= value <= 1092 * 105 calls will be made to get and put.The LFU (Least Frequently Used) Cache requires designing a data structure that supports get and put operations in O(1) time while evicting the least frequently used key when capacity is exceeded. The main challenge is efficiently tracking both access frequency and recency among keys with the same frequency.
A common approach combines a hash map with multiple doubly-linked lists. One hash map stores key-to-node mappings for constant-time access, while another structure groups nodes by their frequency. Each frequency level maintains its own doubly-linked list to preserve insertion order and support quick updates when a key’s frequency increases.
When a key is accessed, its frequency count increases and the node is moved to the corresponding higher-frequency list. A variable tracking the minFreq helps quickly determine which nodes should be evicted when the cache reaches capacity. This design ensures both updates and lookups remain constant time.
The resulting solution achieves O(1) average time for both operations with O(n) space for storing cache entries and frequency structures.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map + Frequency Doubly Linked Lists | O(1) for get and put (amortized) | O(n) |
NeetCode
In this approach, we use a combination of a HashMap (or Dictionary) and a double linked list to ensure O(1) operations for both get and put. The HashMap stores keys and values as well as a reference to the corresponding node in the double linked list, effectively allowing for quick updates and removals. The double linked list maintains the order of keys based on use frequency and recency to guarantee the correct eviction policy.
Time Complexity: O(1) for get and put operations due to the use of HashMap and Doubly Linked List.
Space Complexity: O(capacity) due to storage of nodes and frequency mappings.
1class Node:
2 def __init__(self, key, value):
3 self.key = key
4 self.value = value
5 self.freq = 1
6 self.prev = None
7 self.next = None
8
9class DoubleLinkedList:
10 def __init__(self):
11 self.head = Node(None, None)
12 self.tail = Node(None, None)
13 self.head.next = self.tail
14 self.tail.prev = self.head
15
16 def add(self, node):
17 p = self.head.next
18 self.head.next = node
19 node.prev = self.head
20 node.next = p
21 p.prev = node
22
23 def remove(self, node):
24 p, n = node.prev, node.next
25 p.next = n
26 n.prev = p
27
28 def pop_tail(self):
29 if self.tail.prev is self.head:
30 return None
31 tail = self.tail.prev
32 self.remove(tail)
33 return tail
34
35class LFUCache:
36 def __init__(self, capacity: int):
37 self.capacity = capacity
38 self.size = 0
39 self.node_map = {}
40 self.freq_map = {}
41 self.min_freq = 0
42
43 def update_freq(self, node):
44 freq = node.freq
45 self.freq_map[freq].remove(node)
46 if not self.freq_map[freq].head.next != self.freq_map[freq].tail:
47 del self.freq_map[freq]
48 if freq == self.min_freq:
49 self.min_freq += 1
50
51 node.freq += 1
52 freq = node.freq
53 if freq not in self.freq_map:
54 self.freq_map[freq] = DoubleLinkedList()
55 self.freq_map[freq].add(node)
56
57 def get(self, key: int) -> int:
58 if key not in self.node_map:
59 return -1
60 node = self.node_map[key]
61 self.update_freq(node)
62 return node.value
63
64 def put(self, key: int, value: int) -> None:
65 if self.capacity == 0:
66 return
67 if key in self.node_map:
68 node = self.node_map[key]
69 node.value = value
70 self.update_freq(node)
71 else:
72 if self.size == self.capacity:
73 list_to_remove = self.freq_map[self.min_freq]
74 tail = list_to_remove.pop_tail()
75 del self.node_map[tail.key]
76 self.size -= 1
77 new_node = Node(key, value)
78 self.node_map[key] = new_node
79 if 1 not in self.freq_map:
80 self.freq_map[1] = DoubleLinkedList()
81 self.freq_map[1].add(new_node)
82 self.min_freq = 1
83 self.size += 1The Python solution involves two custom classes: Node and DoubleLinkedList. The Node class holds key-value pairs, frequency counts, and pointers to previous and next nodes. The DoubleLinkedList class is used to maintain the order based on frequency and recency of use.
The LFUCache class maintains two dictionaries: node_map which maps keys to nodes, and freq_map which maps frequencies to linked lists. The cache operations (get/put) are implemented to update the frequency of nodes appropriately and handle cache capacity by removing the least frequently and recently used nodes when needed.
The OrderedDict based approach uses Python's built-in OrderedDict to efficiently track keys while maintaining the insertion order. By managing the dictionary's order, we can track the frequency of access and modify it when performing get or put operations. This may not offer the theoretical O(1) complexity for all operations but is a practical solution with simplicity in Python.
Time Complexity: Average O(1) for both get and put, due to the effectiveness of OrderedDict for these operations.
Space Complexity: O(capacity) for storing nodes and their frequency mappings.
1from collections import defaultdict, OrderedDict
2
3class LFUCache:
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, LFU Cache is a well-known system design and data structure problem often discussed in top tech interviews. It tests knowledge of hash tables, linked lists, and efficient design patterns for constant-time operations.
The optimal approach uses a combination of hash maps and doubly-linked lists to maintain frequency groups. This design allows both get and put operations to run in O(1) time while efficiently tracking the least frequently used elements.
Tracking the minimum frequency helps quickly identify which key should be evicted when the cache reaches capacity. Since LFU removes the least frequently used item, maintaining this value avoids scanning all entries.
A hash map paired with frequency-based doubly-linked lists is the most common structure. The hash map provides constant-time key lookup, while the doubly-linked lists manage ordering within each frequency level and support fast updates.
The OrderedDict solution keeps track of keys and their frequencies in separate dictionaries. key_freq_map maps the key to its frequency, while freq_map has OrderedDicts keyed by frequency with keys as their values. This way, we can update both frequency and recency of accesses.
With the built-in nature of Python's OrderedDict, the implementation remains concise and takes advantage of existing functionality to manage ordering effectively, even if all operations might not run in strict O(1) time.