DescriptionQ931
Q931FWArchASIC interview problem
Implement an O(1) LRU cache
TechniquesPythonLRUHash mapDoubly linked list
DifficultyHard
TopicData Structures
LanguagePython
Requirements4 checkpoints
01
Problem
Implement a fixed-capacity least-recently-used cache with average O(1) get and put. A successful get and every put make the key most recently used.
Example input and output
Use this case to check your interpretationInput
capacity=2; put(1,A), put(2,B), get(1), put(3,C)Output
get(1)=A; key 2 is evicted; LRU-to-MRU order is [1, 3]Explanation
The successful lookup promotes key 1, making key 2 the single eviction victim when key 3 arrives.
02
Requirements (4)
- Reject nonpositive capacity and return -1 for a missing key.
- Use a hash map from key to node and a doubly linked list ordered from most to least recently used.
- Updating an existing key must update its value and recency without changing cache size.
- Inserting past capacity must evict exactly the least-recently-used key from both structures.