LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
Constraints:
- 1 <= capacity <= 1000
- 0 <= key <= 1000
- 0 <= value <= 1000
- At most 3000 operations will be performed.
Examples:
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); lRUCache.put(2, 2); lRUCache.get(1); // return 1 lRUCache.put(3, 3); // evict key 2 lRUCache.get(2); // return -1 (not found) lRUCache.put(4, 4); // evict key 1 lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4
Solutions
Hash Table and Doubly Linked List
We use a hash table to store the keys and values, and a doubly linked list to keep track of the order of the elements. When we get a key, we move it to the end of the list. When we put a key, we add it to the end of the list and remove the first element if the list is full.
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) return -1;
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
put(key, value) {
if (this.cache.has(key)) this.cache.delete(key);
this.cache.set(key, value);
if (this.cache.size > this.capacity)
this.cache.delete(this.cache.keys().next().value);
}
}
Follow-up:
How would you implement the LRU cache if you were not allowed to use a hash table?
