Implement an LRU Cache with `get(key)` and `put(key, value)` methods. It has a max capacity. When full, remove the least recently used item.
Problem Statement
Implement an LRU Cache with `get(key)` and `put(key, value)` methods. It has a max capacity. When full, remove the least recently used item.
Complexity
Time Complexity: -
Space Complexity: -
Hints
š” Hint 1:
LRU = Least Recently Used. The item not accessed for the longest time gets evicted.
š” Hint 2:
Use a Map ā it maintains insertion order. Move accessed keys to the end.
š” Hint 3:
On get/put, delete the key and re-set it to move it to the end. On put, if full, delete the first (oldest) key.
ā
Solution:
```javascript
class LRUCache {
constructor(capacity) { this.capacity = capacity; this.cache = new Map(); }
get(key) {
if (!this.cache.has(key)) return -1;
const val = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, val);
return val;
}
put(key, value) {
this.cache.delete(key);
this.cache.set(key, value);
if (this.cache.size > this.capacity) {
this.cache.delete(this.cache.keys().next().value);
}
}
}
```