Amazon Interview Question: Your LRU Cache Works. Now Make It Expire.

walkthrough of expiration, stale timers, and the small detail that can delete the wrong value.

You have the hash map.

You have the linked list.

Your LRU cache passes the example, and you are mentally packing up your interview nerves.

Then the follow-up arrives: every entry needs an expiration time, and you cannot keep scanning the entire cache to find what has expired.

Lovely.

Our tidy little data structure has acquired a calendar.

I like this question because you can understand the first bug with two entries and five seconds. No giant architecture diagram required. Once we fix that bug, a second one appears when somebody updates a key before its old timer fires.

This TTL-aware LRU cache question from a reported Amazon interview. The prompt is freely readable. Below is my own worked design with explicit choices for the missing details, rather than a claim about Amazon’s exact implementation requirements.

Start with the promise your cache makes

LRU means least recently used. When the cache runs out of room, it removes the entry that has gone longest without being used. TTL means time to live: after a deadline, a stored value is no longer eligible to be returned.

Those rules answer different questions. Recent use tells us what to keep when space is tight. Expiration tells us what we are still allowed to serve.

For our example, let’s agree on a small contract:

• Capacity counts entries. We will use a limit of two, and remove expired entries before evicting a valid one for space.
• A write replaces the value and its deadline. A successful read refreshes recency but does not extend that deadline.
• The deadline is exclusive. At now >= expires_at, the lookup is a miss, even if cleanup has not run.
• Zero capacity stores nothing. A nonpositive TTL removes an existing value for that key and retains no replacement. Negative capacity is rejected.

These are design choices we can discuss with an interviewer. If reads are supposed to renew the TTL, we are building a different policy and must update the expiration machinery on each hit.

Read something recently. Watch it expire anyway.

Imagine the following sequence, with times measured in seconds from the start of our example:

1. At time 0, write A with a TTL of 5. Its deadline is 5.
2. At time 1, write B with a TTL of 30. Its deadline is 31.
3. At time 4, read A. It is a hit, so A becomes the most recently used entry. Its deadline stays 5.
4. At time 5, read A again. This must be a miss. B is older in recency order, but it is still valid.

Here is the trap: checking only the least-recently-used end cannot find every expired entry. At time 5, that end contains B. The expired entry is A, sitting proudly at the most-recent end.

Our cache has remembered who was popular. It still needs to remember who is allowed to stay.

If we insert C at time 5, first remove expired A, then keep B and C. Evicting B while retaining expired A would spend a perfectly useful slot on data we cannot return.

Give recency and expiration their own indexes

Keep the familiar LRU foundation: a hash map from key to entry, plus a doubly linked list ordered from least to most recently used. Each entry holds its value, deadline, and links to its neighbors.

Lookup uses the map and valid hit moves its node to the most-recent end. Removing a known node from both structures takes expected constant time under ordinary hash-map assumptions.

Now add an expiration min-heap. Its smallest deadline is available at the root, so cleanup can process due events and stop as soon as the earliest remaining event is in the future.

I prefer drawing these as separate orders before writing code. In our example, recency says B → A, while expiration says A at 5 → B at 31. That tiny drawing explains why one list cannot do both jobs.

Checking a deadline during get protects correctness. Processing the heap reclaims space. A late cleanup pass may leave an expired entry in memory temporarily; it must never make that entry a valid cache hit.

For elapsed TTLs within this process, use a monotonic clock. Python’s monotonic clock documentation explains that it cannot go backwards and is unaffected by system-clock updates. These deadlines are process-local timing values, not timestamps to persist across a reboot.

Your old timer has no idea you rewrote the value

Okay, now for the bug I want us to catch before declaring victory. Start a separate example:

t = 0: put A = old_value, TTL = 5   # deadline 5
t = 3: put A = new_value, TTL = 20  # deadline 23
t = 5: the original expiration event becomes due

If that old event simply deletes key A, it removes the newer value eighteen seconds early. The heap did exactly what we asked. We asked an incomplete question.

Attach a unique write token to each replacement. The current entry stores that token, and its heap event stores (deadline, token, key). When an event becomes due, it may delete the entry only if its token still matches.

Use a cache-wide increasing counter, or another identity that cannot be reused while old events exist. Resetting a per-key counter after deletion creates a sneaky replay: an old token 1 can match a newly created token 1 for the same key.

Here is the expiration core in Python. It is a focused fragment, not a complete cache class: entries is the current map, expiry_heap contains the event tuples, and remove_current removes the entry from both the map and recency list. The caller holds the cache lock throughout.

import heapq
def expire_due(now, expiry_heap, entries, remove_current):
    while expiry_heap and expiry_heap[0][0] <= now:
        deadline, token, key = heapq.heappop(expiry_heap)
        current = entries.get(key)
        if current is None:
            continue
        if current.token != token:
            continue
        remove_current(key)

In our rewrite example, the due event carries token 1 and the current entry carries token 2. We discard the event and keep A. At time 23, token 2’s own event can remove it.

Keeping the token before the key in the tuple also breaks equal-deadline ties without comparing keys, provided those tokens are globally unique within this cache.

Walk one read and one write all the way through

Now we have enough machinery to make the operations precise. For this simple design, one lock protects the map, list, heap, and token counter. Sample the clock after acquiring that lock.

For a read: look up the entry. If it is missing, return a miss. If its deadline has arrived, remove it from the map and list, then return a miss. Otherwise, move it to the most-recent end and return its value without changing its deadline.

For a write: process heap events due at the sampled time, remove any existing entry for this key, then apply the zero-capacity and nonpositive-TTL rules. If storing a replacement, assign a fresh token, compute its deadline, add it to the map and most-recent end, and push its expiration event. If capacity is exceeded, remove the least-recently-used entry.

Every removal goes through the same helper, so the map and list stay consistent. Old heap events may remain after a rewrite, expiration-on-read, or capacity eviction; the token check makes them harmless when processed.

Notice that a hit changes the recency list. A read-only lock around get therefore does not protect this design. Also, checking a token and deleting the corresponding entry must happen under the same lock; otherwise a concurrent rewrite can slip between those steps.

Keep slow database loads and user callbacks outside that lock. Coordinating a loader with concurrent writes is a separate extension; this exercise implements explicit get and put operations.

Be honest about the price of that heap

Adding TTL changes the complexity story. Let H be the number of heap records, including stale ones.

• A read without global cleanup or heap rebuilding takes expected O(1) work, excluding lock contention.
• A write with no due events takes O(log H) for its heap insertion, plus expected constant-time map and list work.
• Processing k due events costs O(k log H). A large expiration burst can make one foreground write slow.

Stale records also consume memory. Rewrite one key a million times with long TTLs and the cache can contain one value plus a million expiration records. A capacity limit on entries does not bound that heap.

For a compact first implementation, we can rebuild the heap from current entries when its size exceeds a threshold such as 2 × entry_count + 64, checked after mutations. This is an occasional linear rebuild, not a periodic full-table expiration scan, and it still creates a latency spike. A read that removes an expired entry can trigger that maintenance too, so its worst-case cost is no longer constant.

If avoiding those full traversals is a hard requirement, use an indexed heap instead: maintain each key’s heap position and update or remove its event in O(log n). That keeps one expiration record per entry, at the cost of more bookkeeping.

A background cleaner can spread work out, but it does not magically settle capacity policy. If cleanup is capped and expired entries remain, a foreground write must either finish enough cleanup, defer admission, or accept that it might evict valid data first. Our simple version drains due events before insertion.

Finish with a tiny timeline you can defend

Before adding more machinery, use an injectable clock and reason through the moments that distinguish the policies. There is no need to make a practice exercise wait five actual seconds.

Try implementing the design from these cases, then ask a friend to change one rule: reads now extend TTL, capacity is measured in bytes, or expired entries must be reclaimed while the cache is idle. Explain which structure changes and what work becomes more expensive.

I want to leave this question with three things I can explain comfortably: why recent use does not imply validity, why an old expiration event cannot delete a new value, and where the cleanup cost goes.

Once those answers fit together, the cache diagram stops being a collection of memorised boxes. You can follow a value from insertion to removal and account for every decision along the way.

If you enjoy working through interview questions like this, follow Emily or subscribe for the next walkthrough. Bring your neat little solution; we will give it one interesting complication and figure it out together.

~ Emily