Questions
50 of 59
What is an LRU Cache? How do you implement it using a Hash Map and Doubly Linked List?
Difficulty: 4/10
LRU Cache
An LRU, or Least Recently Used, cache evicts the item that has not been accessed for the longest time. To achieve O(1) average get and put operations, combine a Hash Map for direct key lookup with a doubly linked list for maintaining recency order. The most recently used item is placed at the front and the least recently used item at the back.
javascript
- 1
Hash Map provides O(1) average lookup.
- 2
Doubly linked list provides O(1) removal and insertion when a node is known.
- 3
get: O(1) average.
- 4
put: O(1) average.
- 5
Eviction removes the tail node.
Follow-up Questions
- How would you make an LRU cache thread-safe?
- What is the difference between LRU and LFU?