Algorithms and Data Structures · Middle · Question 27 of 75
How is an LRU cache with O(1) get and put usually built?
- 1A min-heap ordered by the time each key was added
- ✓Correct answer: A hash map plus a doubly linked list ordered by recent use
- 3A sorted array of keys with binary search
Explanation
The map finds a node by key; the list moves it to the front in O(1) and drops the tail when full. In JavaScript a Map alone works: it keeps insertion order, so delete and re-set a key on access and evict map.keys().next().value.