-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathlfu_cache.dart
303 lines (245 loc) · 9.25 KB
/
lfu_cache.dart
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
/*
-* 460. LFU Cache*-
Design and implement a data structure for a Least Frequently Used (LFU) cache.
Implement the LFUCache class:
LFUCache(int capacity) Initializes the object with the capacity of the data structure.
int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, 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 used key would 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 <= 104
0 <= key <= 105
0 <= value <= 109
At most 2 * 105 calls will be made to get and put.Design and implement a data structure for a Least Frequently Used (LFU) cache.
Implement the LFUCache class:
LFUCache(int capacity) Initializes the object with the capacity of the data structure.
int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, 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 used key would 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 <= 104
0 <= key <= 105
0 <= value <= 109
At most 2 * 105 calls will be made to get and put.
*/
/*
class LFUCache {
LFUCache(int capacity) {
}
int get(int key) {
}
void put(int key, int value) {
}
}
*/
// class LFUCache {
// late int capacity;
// int minFreq = 0;
// HashMap<int, int> keyToVal = HashMap();
// HashMap<int, int> keyToFreq = HashMap();
// HashMap<int, LinkedHashSet<int>> freqToLRUKeys = HashMap();
// LFUCache(int capacity) {
// this.capacity = capacity;
// }
// int get(int key) {
// if (!keyToVal.containsKey(key)) return -1;
// final int freq = keyToFreq[key] ?? 0;
// freqToLRUKeys[freq]?.remove(key);
// if (freq == minFreq && freqToLRUKeys[freq]!.isEmpty) {
// freqToLRUKeys.remove(freq);
// ++minFreq;
// }
// // Increase key's freq by 1
// // Add this key to next freq's list
// putFreq(key, freq + 1);
// return keyToVal[key] ?? 0;
// }
// void put(int key, int value) {
// if (capacity == 0) return;
// if (keyToVal.containsKey(key)) {
// keyToVal[key] = value;
// get(key); // Update key's count
// return;
// }
// if (keyToVal.length == capacity) {
// // Evict LRU key from the minFreq list
// final int keyToEvict = freqToLRUKeys[minFreq]...iterator.current;
// freqToLRUKeys[minFreq]?.remove(keyToEvict);
// keyToVal.remove(keyToEvict);
// }
// minFreq = 1;
// putFreq(key, minFreq); // Add new key and freq
// keyToVal[key] = value; // Add new key and value
// }
// void putFreq(int key, int freq) {
// keyToFreq[key] = freq;
// freqToLRUKeys.putIfAbsent(freq, () => LinkedHashSet());
// freqToLRUKeys[freq]?.add(key);
// }
// }
// import 'dart:collection';
// class Node {
// late int key;
// late int val;
// late Node next;
// late Node prev;
// int freq = 1;
// Node(int k, int v) {
// key = k;
// val = v;
// }
// }
// class DoublyLinkedList {
// late Node head;
// late Node tail;
// DoublyLinkedList() {
// head = Node(-1, -1);
// tail = Node(-1, -1);
// head.next = tail;
// tail.prev = head;
// }
// void addNode(Node v) {
// Node next = head.next;
// head.next = v;
// v.prev = head;
// head.next = v;
// v.next = next;
// next.prev = v;
// }
// Node removeNode() {
// Node node = tail.prev;
// node.prev.next = tail;
// tail.prev = node.prev;
// return node;
// }
// Node removeNodeAt(Node v) {
// Node prev = v.prev;
// Node next = v.next;
// prev.next = next;
// next.prev = prev;
// return v;
// }
// bool isEmpty() {
// if (head.next == tail) return true;
// return false;
// }
// }
// class LFUCache {
// HashMap<int, DoublyLinkedList> freqList = HashMap<int, DoublyLinkedList>();
// HashMap<int, Node> lfuCache = HashMap<int, Node>();
// late int capacity;
// late int minFreq;
// LFUCache(int capacity) {
// this.capacity = capacity;
// minFreq = 1;
// }
// int get(int key) {
// if (lfuCache[key] == null) return -1;
// Node v = lfuCache[key] ?? 0 as Node;
// freqList[v.freq]?.removeNodeAt(v);
// if (freqList[v.freq]!.isEmpty()) {
// if (minFreq == v.freq) {
// minFreq = v.freq + 1;
// }
// }
// v.freq += 1;
// if (freqList[v.freq] == null) {
// DoublyLinkedList d = new DoublyLinkedList();
// d.addNode(v);
// freqList[v.freq] = d;
// } else {
// freqList[v.freq]?.addNode(v);
// }
// return v.val;
// }
// void put(int key, int value) {
// if (capacity == 0) return;
// if (lfuCache[key] != null) {
// Node v = lfuCache[key] ?? 0 as Node;
// freqList[v.freq]?.removeNodeAt(v);
// if (freqList[v.freq]!.isEmpty()) {
// if (minFreq == v.freq) minFreq = v.freq + 1;
// }
// v.freq += 1;
// if (freqList[v.freq] == null) {
// DoublyLinkedList d = new DoublyLinkedList();
// d.addNode(v);
// freqList[v.freq] = d;
// } else {
// freqList[v.freq]?.addNode(v);
// }
// v.val = value;
// } else {
// if (lfuCache.length == capacity) {
// Node v = freqList[minFreq]!.removeNode();
// lfuCache.remove(v.key);
// }
// Node newNode = new Node(key, value);
// lfuCache[key] = newNode;
// if (freqList[1] != null) {
// freqList[1]?.addNode(newNode);
// } else {
// DoublyLinkedList d = new DoublyLinkedList();
// d.addNode(newNode);
// freqList[1] = d;
// }
// minFreq = 1;
// }
// }
// }