Level:
Topic: 
Similar Problem:
Design and implement a data structure for a Least Frequently Used (LFU) cache.
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
Similar to Least Recently Used, but with one more variable of frequency
- Doubly Linked List - to maintain the from most recently used nodes to least recently used nodes
- Hash Map - to store every nodes that's in the list so every node can be easily removed
- Frequency Hash Map - each frequency corresponds to a doubly linked list, so every time to get the least frequently used, it must be the min freq list's tail node.
- Minimum Frequency - the minimum frequency is for locating the least frequent doubly linked list
Structure of Doubly Linked List: (Same as LRU but with an extra frequency variable for the node class)
- keep a head and tail counter node to locate the whole list
- every new know is being added to the front of the list
- if the list is empty (head is null), set head and tail to the new added node
- else, put it in front of head and let head point to the new node
- the tail node is always the least recently used
- when removing the node
- if the it's the head node
- have head point to the next
- if both head and tail, means there is only one node in the list, so tail is set to null
- not head node, it's gotta be any node between head.next and tail
- set the predecessor node to point to its next, it must have a predecessor node.
- if it's a tail node, it does not have a next node, so the tail will be set to its predecessor
- otherwise, just set the succesor to point to current's predecessor
- if the it's the head node
- when removing the tail node
- just use the remove function and but set the node to tail
- since it would also handle the tail node removal
Structure of Least Frequently Used:
- globalize the cache capacity variable
incrementFrequency- increment the node frequency and place in the correct place- remove from the old freq list and update
minFreqif the old freq list is empty - increment the frequency and add to the new freq list to the freqList map
- remove from the old freq list and update
GET- returns the value if the node exists in the hashmap- if not exists, return -1
- otherwise, get the node from hashmap and
incrementFrequencyof the node
PUT- it might be an old key with a new value- check if key already presents in the cache
- if exists, change the value and call
incrementFrequencyso its position will be updated
- if exists, change the value and call
- otherwise
- create the new node with the key and value
- check if the cache is at capacity
- if true, remove the tail node from minFreq list and from the map
- change
minFreqto 1 since current node is a newly added node of a frequency of 1 - add the new node to the front of the 1's freq list
- add the new node to the map
- check if key already presents in the cache
Time: O(1)
Space: O(c)
class Node {
int key;
int val;
int freq;
Node prev;
Node next;
Node(int key, int val) {
this.key = key;
this.val = val;
this.freq = 1;
}
void incrementFreq() {
freq++;
}
void print() {
System.out.print("(" + key + " " + val + " " + freq + ") ");
}
}
class DLL {
Node head;
Node tail;
int count = 0;
DLL () {}
boolean isEmpty() {
if (count == 0)
{
head = null;
tail = null;
}
return count == 0;
}
void addNode(Node node) {
node.next = null;
node.prev = null;
if (head == null) {
head = node;
tail = node;
} else {
head.prev = node;
node.next = head;
head = node;
}
count++;
}
void removeNode(Node node) {
if (node == head) {
if (node == tail)
tail = null;
head = head.next;
} else {
node.prev.next = node.next;
if (node == tail) {
tail = tail.prev;
tail.next = null;
}
else
node.next.prev = node.prev;
}
count--;
}
Node removeLast() {
Node removed = null;
if (tail != null) {
removed = tail;
removeNode(tail);
}
return removed;
}
void print() {
Node curr = head;
while (curr != null) {
curr.print();
curr = curr.next;
}
System.out.println();
}
}
class LFUCache {
private HashMap<Integer, Node> map = new HashMap<>();
private HashMap<Integer, DLL> freqList = new HashMap<>();
private int minFreq = 0;
private int capacity;
public LFUCache(int capacity) {
this.capacity = capacity;
}
private void print() {
for (int key: freqList.keySet()) {
System.out.print(key + ": ");
freqList.get(key).print();
}
System.out.println();
}
private void incrementFreq(Node node) {
// it's guaranteed that node is in the map and freqlist
int freq = node.freq;
DLL list = freqList.get(freq);
list.removeNode(node);
if (list.isEmpty()) {
freqList.remove(freq);
if (minFreq == freq)
minFreq++;
}
freq++;
node.incrementFreq();
if (!freqList.containsKey(freq))
freqList.put(freq, new DLL());
freqList.get(freq).addNode(node);
}
private void removeLFU() {
DLL list = freqList.get(minFreq);
map.remove(list.removeLast().key);
if (list.isEmpty())
freqList.remove(minFreq);
}
// if there isn't this node, return -1
// otherwise
// 1. increment its frequency
// 2. remove it from the old list and remove the list if the list is empty
// 3. add it to the new list according to its new frequency
// 4. update the minimum frequency if necessary
public int get(int key) {
if (!map.containsKey(key))
return -1;
Node node = map.get(key);
this.incrementFreq(node);
return node.val;
}
// if there is this node already
// 1. update its value
// 2. increment its frequency
// otherwise
// 1. check if there exists capacity nodes
// 1.1 if true, remove the minFreq list's last node
// 1.2 otherwise, add to the map and add to its frequency list
public void put(int key, int value) {
if (capacity == 0)
return ;
if (map.containsKey(key)) {
Node node = map.get(key);
node.val = value;
this.incrementFreq(node);
}
else {
if (map.size() == this.capacity)
removeLFU();
Node node = new Node(key, value);
minFreq = 1;
if (!freqList.containsKey(minFreq))
freqList.put(minFreq, new DLL());
freqList.get(minFreq).addNode(node);
map.put(key, node);
}
}
}
/**
* 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);
*/