LRU Cache
HardDesign Patterns30 min5 tests
Implement an LRU (Least Recently Used) Cache with a fixed capacity.
Requirements
get(key)— return the value if it exists, otherwise return-1. Mark as recently used.put(key, value)— insert or update the value. If capacity is exceeded, evict the least recently used item.- Both operations should be O(1) time.
Example
const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 1
cache.put(3, 3); // evicts key 2
cache.get(2); // -1Hints (4)
- JavaScript
Mapmaintains insertion order — the first key is the oldest. - On
get, delete and re-insert to move to the end. - On
put, check capacity and evict the first key from the Map if full. - Use
map.keys().next().valueto get the least recently used key.
Topics
- Design Patterns
Asked at
Google · Amazon · Meta · Microsoft
