Explain the LRU (Least Recently Used) Cache architecture and how to implement it in O(1) time complexity.
Quick Revision Summary
An LRU Cache combines a Hash Map for O(1) lookup with a Doubly Linked List for O(1) order tracking and eviction.
Interactive Practice Mode
Formulate your thoughts or take notes before revealing the model solution.
Saved automatically
Model Answer & Deep-Dive Explanation
An LRU Cache organizes items in order of use, discarding the least recently accessed item when the cache capacity is exceeded. To achieve both get(key) and put(key, value) in strictly O(1) time complexity, we combine two data structures:
- Hash Map: Maps each key to its corresponding Node in a Doubly Linked List, ensuring O(1) search.
- Doubly Linked List: Maintains access order. The most recently used element is moved to the Head; the least recently used element resides at the Tail. Node insertion and removal in a doubly linked list takes O(1) time when the node pointer is known.
Interviewer Evaluation Points & Scoring Rubric
- 1 1. Identifies HashMap + Doubly Linked List pairing. 2. Explains O(1) get and put guarantees. 3. Describes head insertion and tail eviction flow.
Related Questions in Data Structures & Algorithms
How to detect a cycle in a Linked List using Floyd's Cycle-Finding Algorithm?
Intermediate level • 516 views
When would you choose a hash map instead of an array for lookups?
Easy level • 6 views
How do a stack and a queue differ, and where would each be useful?
Easy level • 6 views
How can you find two indices whose values sum to a target in one pass?
Medium level • 6 views
When does breadth-first search find a shortest path, and when is it the wrong choice?
Medium level • 5 views