What is an LRU Cache? How do you implement it using a Hash Map and Doubly Linked List?

Difficulty: 5/10

LRU cache, hash map, doubly linked list

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.

Scenario Questions

0-2 years experience

2-5 years experience

Follow-up Questions