Design an LRU cache
Implement a class LRUCache that holds at most capacity entries and evicts the least recently used one when it overflows. Both operations should take O(1) time on average.
new LRUCache(capacity)creates an empty cacheget(key)returns the stored value and marks the key as recently used, or returns-1if the key is missingput(key, value)inserts or updates the key and marks it as recently used; if the cache now holds more thancapacityentries, remove the least recently used one
Example with const cache = new LRUCache(2):
cache.put(1, 1); cache.put(2, 2); cache.get(1)→1cache.put(3, 3)evicts key2, because key1was used more recentlycache.get(2)→-1cache.put(1, 'one')updates key1without evicting anything
Define LRUCache in the editor. 8 tests will call it.
Hint 1A Map keeps keys in insertion order, and map.keys().next().value is its oldest key.
Hint 2To mark a key as recently used, delete it and set it again so it moves to the end of the Map.
Hint 3In put, delete an existing key before setting it, then evict the oldest key if size is over capacity. In get, check has() rather than the value, because stored values can be falsy.
one clean solution
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.entries = new Map(); // oldest first, most recently used last
}
get(key) {
if (!this.entries.has(key)) return -1;
const value = this.entries.get(key);
this.entries.delete(key); // re-insert to move the key to the end
this.entries.set(key, value);
return value;
}
put(key, value) {
if (this.entries.has(key)) this.entries.delete(key);
this.entries.set(key, value);
if (this.entries.size > this.capacity) {
const oldestKey = this.entries.keys().next().value;
this.entries.delete(oldestKey);
}
}
}