Design and implement a data structure for a Least Frequently Used (LFU) cache.
Implement the LFUCache class:
LFUCache(int capacity)Initializes the object with thecapacityof the data structure.int get(int key)Gets the value of thekeyif thekeyexists in the cache. Otherwise, returns-1.void put(int key, int value)Update the value of thekeyif present, or inserts thekeyif not already present. When the cache reaches itscapacity, 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:
0 <= capacity <= 1040 <= key <= 1050 <= value <= 109- At most
2 * 105calls will be made togetandput.
- After reading the definition of LFU cache, you should probably noticed the biggest difference, that is, we need to be able to tell how "frequent" a key is used and then make a decision when we need to evict it.
- At the same time, we still need to maintain the "recency" of the keys for the same frequency, because we need to evict the least recently used one, so this is indeed an upgrade version of the previous LRU cache.
- Also all the operations need to be done in
O(1)time complexity. - Still, no need to panic here. Let's see what we have so far.
- We have the "Doubly Linked List" (DLL) weapon to evict the least recently used key, we probably can still take advantage of that.
- So what's missing? The frequencies for the keys. Because without this info, we can never make a decision as to evict which key.
- So the question now is "how do we store these frequency info with the keys"?
- First thing, for the keys with same frequency, we probably want to store them in the same DLL, because that way we could evict the least recently used key easily. More info can be found in the previous note LRU cache.
- So naturally, does it mean for different frequencies we should store them in different DLLs? Exactly!
- The idea is gonna be surprisingly simple if we get to this point that we store the frequencies and keys in another HashMap, with key being the frequncy, and value being a DLL with all keys of that frequency.
- This would make the
putapi work nicely, let's try to imagine how it is gonna work. - a) if the key is a new key, we know its frequency is gonna be
1, and if we don't have a DLL with frequency1, then we initlize a new DLL for it. Otherwise, we should already have a DLL for it, and we just need to add this key/value pair to the end of this DLL. - b) if the key is an existing key, then we need to grab the node, delete it from original DLL, increase its frequency and insert it into the DLL with the new frequency (also if the DLL does not exist, we create a new one for it, same logic as above).
- One caviat is that we need to record the "least frequency" separately so that we can evict the intended key when we have to. And in that case, we need to make sure that we keep the "least frequency" updated. For example, when we update the key from least frequent DLL and it happens to be the only key/value pair there, then we need to increase the least frequency by
1, becase current key's frequency will be increased by1. - Another thing that careful readers might find out is that we still miss the "key -> node" info, i.e., how do we find node by key with
O(1)time complexity, we kind of assumed it already exists in the above reasoning. That's easy, we just need another HashMap for it, with key being the key itself, and value being the node in the DLLs, quite fun! - Also let's create a visual representation so everyone gets a clear picture of how this data structure works.
- At this point, the code should make sense now. I tried to add some comments in the code this time, because we can lose track of the intention sometimes, and a piece of comment would make a big difference.
- Thanks for reading, let me know it makes sense to you too.
class Node {
constructor(key=null, value=null) {
this.key = key;
this.val = value;
this.next = this.prev = null;
this.freq = 1;
}
}
class DoublyLinkedList {
constructor() {
this.head = new Node();
this.tail = new Node();
this.head.next = this.tail;
this.tail.prev = this.head;
}
insertHead(node) {
node.prev = this.head;
node.next = this.head.next;
this.head.next.prev = node;
this.head.next = node;
}
removeNode(node) {
const prev = node.prev;
const next = node.next;
prev.next = next;
next.prev = prev;
}
removeTail() {
const node = this.tail.prev;
this.removeNode(node);
return node.key;
}
isEmpty() {
return this.head.next.val == null;
}
}
const LFUCache = function(capacity) {
this.capacity = capacity;
this.currentSize = 0;
this.leastFreq = 0;
this.keyNodeMap = new Map();
this.freqNodeMap = new Map();
};
LFUCache.prototype.get = function(key) {
const node = this.keyNodeMap.get(key);
if (!node) return -1;
this.updateNode(node);
return node.val;
};
LFUCache.prototype.put = function(key, value) {
if (this.capacity == 0) return;
const node = this.keyNodeMap.get(key);
if (!node) {
if (this.currentSize == this.capacity) {
// Evict the least recently used key happens here!
const tailKey = this.freqNodeMap.get(this.leastFreq).removeTail();
this.keyNodeMap.delete(tailKey);
this.currentSize -= 1;
}
// Since it's a new node, we need to increase current size.
this.currentSize += 1;
const newNode = new Node(key, value);
this.insertNode(newNode);
this.keyNodeMap.set(key, newNode);
// We are sure it's gonna be 1, lol.
this.leastFreq = 1;
} else {
node.val = value;
this.updateNode(node);
}
};
LFUCache.prototype.insertNode = function(node) {
if (this.freqNodeMap.get(node.freq) == null) {
this.freqNodeMap.set(node.freq, new DoublyLinkedList());
}
this.freqNodeMap.get(node.freq).insertHead(node);
}
/**
* 1) First it removes the node from current DLL,
* 2) If its frequency is leastFreq and its the only node in the DLL, increase the leastFreq,
* 3) Increase current node's frequency and insert it to the new DLL.
* Note that after step 1), the DLL could be an empty DLL, instead of clearing the frequency from the map,
* and deleting the empty DLL, we keep it empty, and no need to init a new DLL for the next key with this
* frequency, and potentially save some work, not bad!
*/
LFUCache.prototype.updateNode = function(node) {
this.freqNodeMap.get(node.freq).removeNode(node);
if (node.freq == this.leastFreq && this.freqNodeMap.get(node.freq).isEmpty()) {
this.leastFreq += 1;
}
node.freq += 1;
this.insertNode(node);
}