Published Apr 07, 2022
[
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.
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
1 <= capacity <= 30000 <= key <= 1040 <= value <= 10^52 * 10^5 calls will be made to get and put.O(1) get requires HashMap.O(1) time, Doubly
Linked List.// Doubly Linked List node that stores key, value
class Node {
key: number
value: number;
prev: Node = null
next: Node = null;
constructor(key, value){
this.key = key;
this.value = value;
}
}
class LRUCache {
private capacity: number
// stores key to Node
private cache;
// left most node, least recently used
private LRU: Node
// right most node, most recently used
private MRU: Node;
constructor(capacity: number) {
this.capacity = capacity;
this.cache = {}
this.LRU = new Node(0, 0)
this.MRU = new Node(0, 0);
this.LRU.next = this.MRU;
this.MRU.prev = this.LRU;
}
// remove a node from list
remove(node: Node){
const next: Node = node.next, prev: Node = node.prev;
prev.next = next;
next.prev = prev;
}
// add a node before MRU
add(node: Node){
const prev: Node = this.MRU.prev, next: Node = this.MRU;
prev.next = node;
next.prev = node;
node.prev = prev;
node.next = next;
}
get(key: number): number {
// if key exists in cache, update node & return the value
if(key in this.cache){
this.remove(this.cache[key])
this.add(this.cache[key])
return this.cache[key].value;
}
return -1;
}
put(key: number, value: number): void {
// remove if exists
if(key in this.cache){
this.remove(this.cache[key])
}
// update cache & list
this.cache[key] = new Node(key, value);
this.add(this.cache[key])
if(Object.keys(this.cache).length > this.capacity){
const LRUNode: Node = this.LRU.next;
this.remove(LRUNode)
delete this.cache[LRUNode.key]
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/
// Fortunately JS/TS has a very convenient structure called Map, which behaves like an object, with the particularity of respecting insertion order of keys.
// So we know if we add a key, it will be at the end of the object, and the first inserted key will be at the beginning.
// The "key" (haha) is to be sure to remove keys and re-add it at the end of the map when interacted with.
class LRUCache {
capacity: number;
map: Map<number, number>;
constructor(capacity: number) {
this.capacity = capacity;
this.map = new Map();
}
get(key: number): number {
const value = this.map.get(key);
if (value === undefined) return -1;
this.map.delete(key);
this.map.set(key, value);
return value;
}
put(key: number, value: number): void {
// remove last element to avoid overflow, only if it does not have
// the inserted key is a new key
if (this.map.size >= this.capacity && !this.map.has(key)) {
const firstKey = this.map.keys().next().value;
this.map.delete(firstKey);
}
this.map.delete(key);
this.map.set(key, value);
}
}