forked from varunu28/LeetCode-Java-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLFU Cache.java
More file actions
115 lines (105 loc) · 3.1 KB
/
LFU Cache.java
File metadata and controls
115 lines (105 loc) · 3.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
class LFUCache {
private final Map<Integer, Node> keyToNodeMap;
private final Map<Integer, Node[]> frequencyToNodeMap;
private final Map<Integer, Integer> keyToFrequencyMap;
private int capacity;
private int currentCapacity;
public LFUCache(int capacity) {
this.capacity = capacity;
this.currentCapacity = 0;
this.keyToNodeMap = new HashMap<>();
this.frequencyToNodeMap = new TreeMap<>();
this.keyToFrequencyMap = new HashMap<>();
}
public int get(int key) {
if (!keyToNodeMap.containsKey(key)) {
return -1;
}
Node node = keyToNodeMap.get(key);
removeNode(node);
int currentFrequency = keyToFrequencyMap.get(key);
int newFrequency = currentFrequency + 1;
keyToFrequencyMap.put(key, newFrequency);
addNodeToFrequencyHead(node, newFrequency);
return node.val;
}
public void put(int key, int value) {
if (this.capacity == 0) {
return;
}
removeNodeIfCapacityReached(key);
Node node = getNode(key, value);
int newFrequency = keyToFrequencyMap.getOrDefault(key, 0) + 1;
keyToFrequencyMap.put(key, newFrequency);
keyToNodeMap.put(key, node);
if (newFrequency > 1) {
removeNode(node);
}
addNodeToFrequencyHead(node, newFrequency);
}
private void removeNodeIfCapacityReached(int key) {
if (!keyToNodeMap.containsKey(key) && this.currentCapacity == capacity) {
for (Integer freq : frequencyToNodeMap.keySet()) {
Node[] nodes = frequencyToNodeMap.get(freq);
if (nodes[1].prev.val == -1) {
continue;
}
Node toRemove = nodes[1].prev;
removeNode(toRemove);
keyToNodeMap.remove(toRemove.key);
keyToFrequencyMap.remove(toRemove.key);
this.currentCapacity--;
break;
}
}
}
private Node getNode(int key, int value) {
Node node;
if (keyToNodeMap.containsKey(key)) {
node = keyToNodeMap.get(key);
removeNode(node);
node.val = value;
} else {
this.currentCapacity++;
node = new Node(value, key);
}
return node;
}
private void addNodeToFrequencyHead(Node node, int newFrequency) {
if (!frequencyToNodeMap.containsKey(newFrequency)) {
Node head = new Node(-1, Integer.MIN_VALUE);
Node tail = new Node(-1, Integer.MAX_VALUE);
head.next = tail;
tail.prev = head;
frequencyToNodeMap.put(newFrequency, new Node[]{head, tail});
}
Node headNode = frequencyToNodeMap.get(newFrequency)[0];
Node nextToHead = headNode.next;
nextToHead.prev = node;
node.next = nextToHead;
headNode.next = node;
node.prev = headNode;
}
private void removeNode(Node node) {
Node prevNode = node.prev;
Node nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}
private static class Node {
int val;
int key;
Node next;
Node prev;
public Node(int val, int key) {
this.val = val;
this.key = key;
}
}
}
/**
* 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);
*/