LRU Cache And O(1) Data Structures
Asked of: Software Engineer
Last updated

What's being tested
This tests O(1) mutable data structure design, usually combining a hash map with a doubly linked list to implement cache lookup, recency updates, insertion, and eviction. Interviewers are probing whether you can preserve invariants under get, put, update-existing, capacity overflow, and missing-key cases.
Patterns & templates
-
Hash map + doubly linked list — map
key -> node; list stores recency order;getandputareO(1)average time. -
Sentinel head/tail nodes simplify list mutations —
addToFront(node),remove(node),moveToFront(node),popTail()avoid null-heavy edge cases. -
LRU semantics — successful
get(key)updates recency;put(existingKey, value)updates value and recency; eviction removes least-recently-used node. -
Capacity handling — after inserting a new key, if
size > capacity, evict tail node and delete its key from the map. -
Cache optimization framing — define cache key, cached value, invalidation/TTL, memory bound, expected hit rate, and worst-case behavior before coding.
-
Complexity contract — state
O(1)average time due to hash map,O(capacity)space; note hash collision worst case if interviewer asks. -
Thread-safety extension — single mutex is simple and correct; finer-grained locking improves throughput but complicates recency-list consistency.
Common pitfalls
Pitfall: Using only a hash map gives fast lookup but no
O(1)way to find and remove the least-recently-used item.
Pitfall: Forgetting that
getmust update recency causes subtle failures on eviction-order tests.
Pitfall: Evicting from the list but not deleting from the map leaves stale nodes and incorrect future lookups.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Implement Cache and Count ComponentsAmazon · Software Engineer · Technical Screen · medium
- Optimize with a cache/hash mapAmazon · Software Engineer · Technical Screen · Medium
- Optimize with caching or hash mapsAmazon · Software Engineer · Technical Screen · Medium
- Implement LRU cache with O(1) opsAmazon · Software Engineer · Onsite · Medium
Related concepts
- LRU CacheCoding & Algorithms
- LRU Cache Design And PersistenceCoding & Algorithms
- Mutable Data Structures And O(1) DesignCoding & Algorithms
- Linked Lists, Pointers, Caches, And In-Memory StoresCoding & Algorithms
- Linked Lists, Stacks, Caches, And Pointer TechniquesCoding & Algorithms
- Caching And Stateful Data Structure DesignCoding & Algorithms