How would you implement an LRU cache with expected constant-time get and put operations?
Interactive Practice Mode
Formulate your thoughts or take notes before revealing the model solution.
Saved automatically
Model Answer & Deep-Dive Explanation
Combine a hash map from keys to nodes with a doubly linked list ordered by recent use. On a hit, move the node to the most-recent end; on an update, change its value and move it. On insertion at capacity, remove the least-recent node from both structures. These operations are expected O(1) with ordinary hash-map assumptions. Handle capacity zero, overwrites, and missing keys explicitly. In concurrent code, protect the map and list as one invariant; independently locking each structure can leave them inconsistent.
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
How do a stack and a queue differ, and where would each be useful?
Easy level • 8 views
When would you choose a hash map instead of an array for lookups?
Easy level • 7 views
How can you find two indices whose values sum to a target in one pass?
Medium level • 7 views
When does breadth-first search find a shortest path, and when is it the wrong choice?
Medium level • 6 views