Design an LRU Cache
Design a data structure for a least-recently-used (LRU) cache with a fixed capacity. Implement get(key) and put(key, value), both in O(1) average time. When the cache is full, put evicts the least recently used entry.
Hints
Hint 1
You need O(1) lookup and O(1) reordering. Which two structures combine to give you both?
Hint 2
A doubly linked list makes move-to-front and evict-from-back constant time; the map points at its nodes.