Problem
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 usedkeywould 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 <= 10^40 <= key <= 10^50 <= value <= 10^9At most
2 * 10^5calls will be made togetandput.
Solution (Java)
class LFUCache {
private static class Node {
Node prev;
Node next;
int key = -1;
int val;
int freq;
}
private final Map<Integer, Node> endOfBlock;
private final Map<Integer, Node> map;
private final int capacity;
private final Node linkedList;
public LFUCache(int capacity) {
endOfBlock = new HashMap<>();
map = new HashMap<>();
this.capacity = capacity;
linkedList = new Node();
}
public int get(int key) {
if (map.containsKey(key)) {
Node newEndNode = map.get(key);
Node endNode;
Node currEndNode = endOfBlock.get(newEndNode.freq);
if (currEndNode == newEndNode) {
findNewEndOfBlock(newEndNode);
if (currEndNode.next == null || currEndNode.next.freq > newEndNode.freq + 1) {
newEndNode.freq++;
endOfBlock.put(newEndNode.freq, newEndNode);
return newEndNode.val;
}
}
if (newEndNode.next != null) {
newEndNode.next.prev = newEndNode.prev;
}
newEndNode.prev.next = newEndNode.next;
newEndNode.freq++;
if (currEndNode.next == null || currEndNode.next.freq > newEndNode.freq) {
endNode = currEndNode;
} else {
endNode = endOfBlock.get(newEndNode.freq);
}
endOfBlock.put(newEndNode.freq, newEndNode);
if (endNode.next != null) {
endNode.next.prev = newEndNode;
}
newEndNode.next = endNode.next;
endNode.next = newEndNode;
newEndNode.prev = endNode;
return newEndNode.val;
}
return -1;
}
public void put(int key, int value) {
Node endNode;
Node newEndNode;
if (capacity == 0) {
return;
}
if (map.containsKey(key)) {
map.get(key).val = value;
get(key);
} else {
if (map.size() == capacity) {
Node toDelete = linkedList.next;
map.remove(toDelete.key);
if (toDelete.next != null) {
toDelete.next.prev = linkedList;
}
linkedList.next = toDelete.next;
if (endOfBlock.get(toDelete.freq) == toDelete) {
endOfBlock.remove(toDelete.freq);
}
}
newEndNode = new Node();
newEndNode.key = key;
newEndNode.val = value;
newEndNode.freq = 1;
map.put(key, newEndNode);
endNode = endOfBlock.getOrDefault(1, linkedList);
endOfBlock.put(1, newEndNode);
if (endNode.next != null) {
endNode.next.prev = newEndNode;
}
newEndNode.next = endNode.next;
endNode.next = newEndNode;
newEndNode.prev = endNode;
}
}
private void findNewEndOfBlock(Node node) {
Node prev = node.prev;
if (prev.freq == node.freq) {
endOfBlock.put(node.freq, prev);
} else {
endOfBlock.remove(node.freq);
}
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
Solution (Javascript)
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);
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).