I found this one on VOZ forum when a member shared about Shopee coding interview. And this is one of the most interesting problems on Leetcode in my opinion. I need to combine both fancy data structures HashMap and LinkedList in my solution. Today, to enjoy my weekend, I will explain how I implement the LFU cache.
I. Preparation
A cache always has 2 main functions: get and put. And the requirements here are get and put method must run in O(1) average time complexity.
=> we will store data in a Hashmap.
we invalidate and remove the least frequently used key. When there are 2 or more keys with the same frequency, we will remove the least recently used key.
=> we will store the frequency of keys in a Hashmap <Frequency, LinkedList of Key> and will maintain the least recently used by the LinkedList of keys in the value.
=> we also need to maintain what is the min frequency of cache, so when you update the freqMap, you also need to update the min frequency.
And this is my note before I implement:
class LFUCache:
- capacity
- min freq
- freqMap: map of (freq, double linked list of nodes)
- cache: map of (key, node)
get:
- if not exist: return -1
- if exist:
- check if the node has freq = min_freq and list size == 0 => min_freq++ (because after that we will increase cur freq by 1)
- increase node frequency by 1
- remove the node from the current LinkedList in freqMap and insert it to the head of the list at freq + 1 key
- return value
- put:
- if exist: update the value of the key in the cache, increase the freq of the node by 1, and update freqMap with the new freq.
- else:
- full capacity: get linked list from freqMap by min freq of cache, remove the last node in freqMap and cache.
- create a new node with freq = 1, reset min freq to 1
- insert to freqMap: get the cur list or create a new list if not exist, add the new one, and put the list again.
- insert into cache.
II. Implementation
Phewwww, here is my implementation:
import java.util.HashMap;
import java.util.Map;
class LFUCache {
private int capacity;
private int minFreq;
private Map<Integer, DoubleLinkedList> freqMap = new HashMap<>();
private Map<Integer, Node> cache = new HashMap<>();
public LFUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (!cache.containsKey(key)) return -1;
Node node = cache.get(key);
updateFreqList(node);
return node.val;
}
public void put(int key, int value) {
if (capacity == 0) return;
if (cache.containsKey(key)) {
Node node = cache.get(key);
node.val = value;
updateFreqList(node);
} else {
if (cache.size() == capacity) {
DoubleLinkedList minFreqList = freqMap.get(minFreq);
Node minNode = minFreqList.removeLast();
cache.remove(minNode.key);
}
Node newNode = new Node(key, value);
minFreq = 1;
DoubleLinkedList curList = freqMap.getOrDefault(1, new DoubleLinkedList());
curList.add(newNode);
freqMap.put(1, curList);
cache.put(key, newNode);
}
}
private void updateFreqList(Node node) {
DoubleLinkedList curList = freqMap.get(node.frequency);
curList.remove(node);
if (node.frequency == minFreq && curList.size == 0) minFreq++;
node.frequency++;
DoubleLinkedList newList = freqMap.getOrDefault(node.frequency, new DoubleLinkedList());
newList.add(node);
freqMap.put(node.frequency, newList);
}
class Node {
int key;
int val;
Node next;
Node prev;
int frequency;
public Node(int k, int v) {
key = k;
val = v;
frequency = 1;
}
}
class DoubleLinkedList {
Node head;
Node tail;
int size;
public DoubleLinkedList() {
this.size = 0;
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
public void add(Node node) {
node.next = head.next;
head.next.prev = node;
node.prev = head;
head.next = node;
size++;
}
public void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
size--;
}
public Node removeLast() {
if (size > 0) {
Node tailNode = tail.prev;
remove(tailNode);
return tailNode;
}
return null;
}
}
}
III. Result
Phewwwww, it's done. I implemented my own doubly linked list, and compare it with when I use LinkedList of Java Core. Surprisingly, my own linked list had better runtime (149ms) while Java core's LinkedList triple (509ms). That may be because the core LinkedList needs to do many other actions (when we add and remove) rather than focusing on only this problem =)))
Okay, that's all for today's post.
IV. Enjoy your weekend
By the way, let's see =))). Autumn has already come. Go out and enjoy now =)))
Enjoy your weekend!
