LFU (Least Frequently Used) Cache is a type of cache eviction algorithm that removes the least frequently used items first when the cache reaches its capacity limit. The idea behind this algorithm is that items that are used less frequently are less likely to be used in the near future, so it makes sense to remove them first to make room for more frequently used items.
Test Cases :
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
Intuition:
- To implement LFU cache, we can use a hashmap to store the key-value pairs, and a doubly linked list to maintain the frequency of each key.
- Every time a key is accessed, we increment its frequency and move it to the appropriate position in the linked list.
- When the cache reaches its capacity limit, we remove the least frequently used key from the head of the linked list.
Approach:
- Create a hashmap to store the key-value pairs and a doubly linked list to maintain the frequency of each key.
- When a key is accessed, check if it exists in the hashmap. If it does, update its value and increment its frequency.
- If the key does not exist in the hashmap, check if the cache has reached its capacity limit. If it has, remove the least frequently used key from the head of the linked list.
- Add the key-value pair to the hashmap and insert it into the appropriate position in the linked list based on its frequency.
Time Complexity:
- The time complexity of getting and setting a key is O(1) on average.
- The time complexity of removing the least frequently used key when the cache reaches its capacity limit is O(1) on average.
Code : C++ / Java / Python / Javascript / Dart:
C++ :
class LFUCache {
int minFreq;
int capacity;
unordered_map<int,pair<int,int>> keyVal;
unordered_map<int,list<int>> freqList;
unordered_map<int,list<int>::iterator> pos;
public:
LFUCache(int capacity) {
this->capacity = capacity;
minFreq = 0;
}
int get(int key) {
if(keyVal.find(key) == keyVal.end())
return -1;
freqList[keyVal[key].second].erase(pos[key]);
keyVal[key].second++;
freqList[keyVal[key].second].push_back(key);
pos[key] = --freqList[keyVal[key].second].end();
if(freqList[minFreq].empty())
minFreq++;
return keyVal[key].first;
}
void put(int key, int value) {
if(!capacity)
return;
if(keyVal.find(key) != keyVal.end()) {
keyVal[key].first = value;
freqList[keyVal[key].second].erase(pos[key]);
keyVal[key].second++;
freqList[keyVal[key].second].push_back(key);
pos[key] = --freqList[keyVal[key].second].end();
if(freqList[minFreq].empty())
minFreq++;
return;
}
if(keyVal.size() == capacity) {
int delKey = freqList[minFreq].front();
keyVal.erase(delKey);
pos.erase(delKey);
freqList[minFreq].pop_front();
}
keyVal[key] = {value,1};
freqList[1].push_back(key);
pos[key] = --freqList[1].end();
minFreq = 1;
}
};
Python :
import collections
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.freq = 1
self.prev = self.next = None
class DLinkedList:
def __init__(self):
self._sentinel = Node(None, None) # dummy node
self._sentinel.next = self._sentinel.prev = self._sentinel
self._size = 0
def __len__(self):
return self._size
def append(self, node):
node.next = self._sentinel.next
node.prev = self._sentinel
node.next.prev = node
self._sentinel.next = node
self._size += 1
def pop(self, node=None):
if self._size == 0:
return
if not node:
node = self._sentinel.prev
node.prev.next = node.next
node.next.prev = node.prev
self._size -= 1
return node
class LFUCache:
def __init__(self, capacity):
self._size = 0
self._capacity = capacity
self._node = dict() # key: Node
self._freq = collections.defaultdict(DLinkedList)
self._minfreq = 0
def _update(self, node):
freq = node.freq
self._freq[freq].pop(node)
if self._minfreq == freq and not self._freq[freq]:
self._minfreq += 1
node.freq += 1
freq = node.freq
self._freq[freq].append(node)
def get(self, key):
if key not in self._node:
return -1
node = self._node[key]
self._update(node)
return node.val
def put(self, key, value):
if self._capacity == 0:
return
if key in self._node:
node = self._node[key]
self._update(node)
node.val = value
else:
if self._size == self._capacity:
node = self._freq[self._minfreq].pop()
del self._node[node.key]
self._size -= 1
node = Node(key, value)
self._node[key] = node
self._freq[1].append(node)
self._minfreq = 1
self._size += 1Java:
package LFUCache;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
public class LFUCache {
private class Node {
int key;
int frequency;
int value;
int time;
public Node(int k, int v, int f) {
key = k;
frequency = f;
value = v;
time = ++timestamp;
}
}
HashMap<Integer, Node> frequencyMap;
PriorityQueue<Integer> frequencyMinHeap;
int timestamp;
private int capacity;
public LFUCache(int capacity) {
frequencyMap = new HashMap<>();
frequencyMinHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer p1, Integer p2) {
int diff = frequencyMap.get(p1).frequency - frequencyMap.get(p2).frequency;
return diff == 0 ? frequencyMap.get(p1).time - frequencyMap.get(p2).time : diff;
}
});
this.capacity = capacity;
timestamp = 0;
}
public int get(int key) {
if (frequencyMap.containsKey(key)) {
Node p = frequencyMap.get(key);
++p.frequency;
p.time = ++timestamp;
// force heapify:
frequencyMinHeap.offer(frequencyMinHeap.poll());
return p.value;
} else {
return -1;
}
}
public void put(int key, int value) {
if (capacity == 0) {
return;
}
if (frequencyMap.containsKey(key)) {
Node p = frequencyMap.get(key);
p.value = value;
p.time = ++timestamp;
++p.frequency;
// force heapify:
frequencyMinHeap.offer(frequencyMinHeap.poll());
} else {
if (frequencyMinHeap.size() == capacity) {
int k = frequencyMinHeap.poll();
frequencyMap.remove(k);
}
Node p = new Node(key, value, 1);
frequencyMap.put(key, p);
frequencyMinHeap.offer(key);
}
}
}var LFUCache = function(capacity) {
this.capacity = capacity;
this.map = new Map();
this.start = null;
function addFirst(key, val) {
let newNode = new Node(key, val);
if (this.start == null) {
this.start = newNode;
} else {
newNode.next = this.start;
this.start.prev = newNode;
this.start = newNode;
}
this.map.set(key, newNode);
}
function removeLFUNode() {
let minNode = this.start;
let node = this.start.next;
while (node != null) {
if (node.count <= minNode.count) {
minNode = node;
}
node = node.next;
}
if (minNode.prev == null) {
this.start = this.start.next;
} else {
let prev = minNode.prev;
let next = minNode.next;
prev.next = next;
if (next != null) {
next.prev = prev;
}
}
this.map.delete(minNode.key);
}
function moveNodeToFirst(node) {
if (node == this.start) return;
let next = node.next;
let prev = node.prev;
prev.next = next;
if (next != null) {
next.prev = prev;
}
node.next = this.start;
this.start.prev = node;
this.start = node;
node.prev = null;
}
this.addFirst = addFirst;
this.removeLFUNode = removeLFUNode;
this.moveNodeToFirst = moveNodeToFirst;
};
/**
* @param {number} key
* @return {number}
*/
LFUCache.prototype.get = function(key) {
if (this.capacity == 0) return -1;
if (this.map.has(key)) {
let node = this.map.get(key);
++node.count;
this.moveNodeToFirst(node);
return node.val;
}
return -1;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LFUCache.prototype.put = function(key, value) {
if (this.capacity == 0) return;
if (this.map.has(key)) {
let node = this.map.get(key);
node.val = value;
this.get(key);
return;
}
if (this.map.size == this.capacity) {
this.removeLFUNode();
}
this.addFirst(key, value);
};
function Node(key, val) {
this.count = 1;
this.key = key;
this.val = val;
this.prev = null;
this.next = null;
};