An LRU cache with O(1) get and put is typically built with…
Options
- A sorted list ordered by last use
- A hash map plus a doubly linked list (Correct option)
- A min-heap ordered by timestamp
- Two stacks that swap their items
Answer
A hash map plus a doubly linked list
Why
LRU = Least Recently Used: when full, remove the item that was used longest ago.
The hash map finds any item in O(1). The doubly linked list keeps items in usage order: move an item to the front when used, remove from the back when full, both O(1).
In Python, OrderedDict (with move_to_end and popitem(last=False)) does exactly this.
Remember
LRU cache = hash map + doubly linked list.