-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlruCache.js
More file actions
126 lines (110 loc) · 3.41 KB
/
lruCache.js
File metadata and controls
126 lines (110 loc) · 3.41 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
116
117
118
119
120
121
122
123
124
125
126
/**
* LeetCode 146. LRU Cache
* https://leetcode.com/problems/lru-cache/
*
* Design a data structure that follows the constraints of a Least Recently
* Used (LRU) cache.
*
* Implement the LRUCache class:
* - LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
* - int get(int key) Return the value of the key if the key exists, otherwise return -1.
* - void put(int key, int value) Update the value of the key if the key exists.
* Otherwise, add the key-value pair to the cache. If the number of keys
* exceeds the capacity from this operation, evict the least recently used key.
*
* The functions get and put must each run in O(1) average time complexity.
*/
class LRUCache {
constructor(capacity) {
this.cap = capacity;
this.map = new Map(); // key -> node
// Sentinel nodes
this.head = { key: 0, val: 0, prev: null, next: null };
this.tail = { key: 0, val: 0, prev: null, next: null };
this.head.next = this.tail;
this.tail.prev = this.head;
}
_remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
_insertBefore(target, node) {
node.prev = target.prev;
node.next = target;
target.prev.next = node;
target.prev = node;
}
get(key) {
if (!this.map.has(key)) return -1;
const node = this.map.get(key);
this._remove(node);
this._insertBefore(this.tail, node); // move to most recent
return node.val;
}
put(key, value) {
if (this.map.has(key)) {
const node = this.map.get(key);
node.val = value;
this._remove(node);
this._insertBefore(this.tail, node);
} else {
if (this.map.size === this.cap) {
// Evict LRU (right after head)
const lru = this.head.next;
this._remove(lru);
this.map.delete(lru.key);
}
const node = { key, val: value, prev: null, next: null };
this._insertBefore(this.tail, node);
this.map.set(key, node);
}
}
}
// Not quite fast enough for LeetCode
// /**
// * @param {number} capacity
// */
// function LRUCache(capacity) {
// this.capacity = capacity;
// this.items = [];
// this.counter = 0;
// }
// /**
// * @param {number} key
// * @return {number}
// */
// LRUCache.prototype.get = function (key) {
// const itemIndex = this.items.findIndex((item) => item.key === key);
// if (itemIndex === -1) return -1;
// const item = this.items[itemIndex];
// this.items[itemIndex] = { ...item, timestamp: this.counter };
// this.counter++;
// return item.value;
// };
// /**
// * @param {number} key
// * @param {number} value
// * @return {void}
// */
// LRUCache.prototype.put = function (key, value) {
// if (this.get(key) !== -1) {
// this.counter++;
// const itemIndex = this.items.findIndex((item) => item.key === key);
// const item = this.items[itemIndex];
// this.items[itemIndex] = { ...item, value, timestamp: this.counter };
// return;
// }
// if (this.items.length === this.capacity) {
// const earliestTouchedItemIndex = this.items.reduce(
// (earliestIndex, currentItem, currentIndex, allItems) =>
// currentItem.timestamp < allItems[earliestIndex].timestamp
// ? currentIndex
// : earliestIndex,
// 0,
// );
// this.items.splice(earliestTouchedItemIndex, 1);
// }
// this.items.push({ key, value, timestamp: this.counter });
// this.counter++;
// };
module.exports = { LRUCache };