LRU Cache
Asked of: Software Engineer
Last updated

What's being tested
LRU cache problems test whether you can combine a hash map with a doubly linked list to support get and put in O(1) time. TTL variants add expiration semantics, requiring careful cleanup without breaking LRU ordering, capacity eviction, or edge-case correctness.
Patterns & templates
-
Hash map + doubly linked list — map
key -> node; list stores recency withheadas most recent andtailas least recent. -
get(key)template — check existence, validate TTL, delete expired nodes, move live node to front, return value inO(1). -
put(key, value)template — update existing live node or insert new node; evict expired entries first, then evict LRU if over capacity. -
TTL timestamping — store
expiresAt = now + ttl; avoid storing remaining TTL because access should not mutate expiration unless explicitly asked. -
Lazy expiration — remove expired entries only during
get/put; simple and usually acceptable, but stale nodes may occupy memory until touched. -
Eager expiration option — use a min-heap by
expiresAtfor cleanup; improves expired eviction but addsO(log n)heap maintenance. -
Concurrency control — for thread-safe variants, guard map and list mutation with a lock; reads are writes because they update recency.
Common pitfalls
Pitfall: Updating the hash map but forgetting to unlink the old linked-list node creates duplicate keys and corrupts eviction behavior.
Pitfall: Treating expired entries as valid during capacity checks can evict the wrong LRU item instead of first removing dead entries.
Pitfall: Assuming
getis read-only; in LRU it must move the node to most-recent position, so it mutates internal state.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
Related concepts
- LRU Cache Design And PersistenceCoding & Algorithms
- LRU Cache And O(1) Data StructuresCoding & Algorithms
- Mutable Data Structures And O(1) DesignCoding & Algorithms
- Caching And Stateful Data Structure DesignCoding & Algorithms
- Linked Lists, Pointers, Caches, And In-Memory StoresCoding & Algorithms
- Linked Lists, Stacks, Caches, And Pointer TechniquesCoding & Algorithms