Hardware interview practice
Implement an O(1) LRU cache
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.
Reviewed example
Work through one case
Input
capacity=2; put(1,A), put(2,B), get(1), put(3,C)Expected output
get(1)=A; key 2 is evicted; LRU-to-MRU order is [1, 3]The successful lookup promotes key 1, making key 2 the single eviction victim when key 3 arrives.
What to cover
Requirements
- 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.