LRU Cache And O(1) Data Structures

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; get and put are O(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 get must 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.