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 constructor(key, value) {
3 this.key = key;
4 this.value = value;
5 this.freq = 1;
6 this.prev = null;
7 this.next = null;
8 }
9}
10
11class DoubleLinkedList {
12 constructor() {
13 this.head = new Node(null, null);
14 this.tail = new Node(null, null);
15 this.head.next = this.tail;
16 this.tail.prev = this.head;
17 }
18
19 add(node) {
20 const nextNode = this.head.next;
21 this.head.next = node;
22 node.prev = this.head;
23 node.next = nextNode;
24 nextNode.prev = node;
25 }
26
27 remove(node) {
28 const prevNode = node.prev;
29 const nextNode = node.next;
30 prevNode.next = nextNode;
31 nextNode.prev = prevNode;
32 }
33
34 popTail() {
35 if (this.tail.prev === this.head) return null;
36 const nodeToRemove = this.tail.prev;
37 this.remove(nodeToRemove);
38 return nodeToRemove;
39 }
40}
41
42class LFUCache {
43 constructor(capacity) {
44 this.capacity = capacity;
45 this.size = 0;
46 this.nodeMap = new Map();
47 this.freqMap = new Map();
48 this.minFreq = 0;
49 }
50
51 updateFreq(node) {
52 const freq = node.freq;
53 const list = this.freqMap.get(freq);
54 list.remove(node);
55 if (!list.head.next !== list.tail) {
56 this.freqMap.delete(freq);
57 if (freq === this.minFreq) {
58 this.minFreq++;
59 }
60 }
61
62 node.freq++;
63 const newFreq = node.freq;
64 if (!this.freqMap.has(newFreq)) {
65 this.freqMap.set(newFreq, new DoubleLinkedList());
66 }
67 this.freqMap.get(newFreq).add(node);
68 }
69
70 get(key) {
71 if (!this.nodeMap.has(key)) return -1;
72 const node = this.nodeMap.get(key);
73 this.updateFreq(node);
74 return node.value;
75 }
76
77 put(key, value) {
78 if (this.capacity === 0) return;
79 if (this.nodeMap.has(key)) {
80 const node = this.nodeMap.get(key);
81 node.value = value;
82 this.updateFreq(node);
83 } else {
84 if (this.size === this.capacity) {
85 const list = this.freqMap.get(this.minFreq);
86 const toRemove = list.popTail();
87 this.nodeMap.delete(toRemove.key);
88 this.size--;
89 }
90
91 const newNode = new Node(key, value);
92 this.nodeMap.set(key, newNode);
93 if (!this.freqMap.has(1)) {
94 this.freqMap.set(1, new DoubleLinkedList());
95 }
96 this.freqMap.get(1).add(newNode);
97 this.minFreq = 1;
98 this.size++;
99 }
100 }
101}The JavaScript solution closely mirrors the Python one, making use of ES6 class syntax. Two classes, Node and DoubleLinkedList, are utilized to manage nodes and frequency lists. The methods exhibit similar logic to their Python counterparts: Nodes are added to and removed from the double linked list, and frequencies are updated in constant time.
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.