LRU Cache

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 with head as most recent and tail as least recent.

• get(key) template — check existence, validate TTL, delete expired nodes, move live node to front, return value in O(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 expiresAt for cleanup; improves expired eviction but adds O(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 get is 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.