Coding Interview: Implement a TTL Cache with Expiration

Question and when it applies

Implement an in-memory cache where every key has a value and an expiration time. get must never return an expired value. Explain the clock, boundary, cleanup, capacity, concurrency, and complexity.

Amazon lists data structures, algorithms, and coding among software-development interview topics and emphasizes applying knowledge. Redis documents TTL and EXPIRE semantics, including remaining lifetime and precision. Unlike LRU or LFU, this problem centers on time semantics and expiration cleanup.

What interviewers assess

Interviewers look for an explicit TTL unit and clock, a correct expiration boundary, cleanup choices, concurrent consistency, capacity behavior, and time and space complexity.

Questions to clarify before answering

• Are TTLs seconds or milliseconds? Does zero expire immediately?
• Is the clock monotonic?
• Must expired entries be removed immediately?
• Is there a maximum capacity or LRU policy?
• How do set, get, and cleanup synchronize?
• Does updating a key reset TTL?
• Is persistence or cross-process sharing required?
• Must cleanup work be bounded?

30-second answer framework

“I store each key’s value and absolute expiresAt in a hash table. get checks a monotonic clock first; if now is at or after expiresAt, it deletes and returns a miss. set replaces the value and TTL. The basic version uses lazy cleanup with amortized O(1) get and O(n) space. A min-heap or bounded scan handles cold entries. Locks or sharding protect hash and cleanup updates. Tests cover zero TTL, equality, refresh, and races.”

Deep answer, step by step

Step 1: Define the item

Store value and expiresAt; no TTL can use infinity. Use one rule, now >= expiresAt, on every path.

Step 2: Implement get and set

get returns a miss for an absent key. For an expired key it deletes before returning a miss. set computes an absolute expiry and updates any cleanup index.

Step 3: Choose a clock

Use a monotonic clock for elapsed time so wall-clock adjustments cannot extend a TTL. Persistence and cross-process designs need an explicit time basis and precision.

Step 4: Choose cleanup

Lazy cleanup is simple but cold keys can consume memory. A min-heap pops the earliest expiry; periodic scans bound work but may delay deletion.

Step 5: Make updates concurrent-safe

set, get, delete, and cleanup must agree on the same value and expiry. Use a global lock, read-write lock, or sharded locks. A heap and table update must be atomic together.

Step 6: Separate capacity from TTL

TTL does not define capacity. At the limit, choose LRU, random eviction, or reject writes. Track eviction separately from expiration.

Step 7: State complexity and pseudocode

The core boundary is:

get(key):
  item = table[key]
  if item is absent: return MISS
  if clock.now() >= item.expiresAt:
    delete table[key]
    return MISS
  return item.value

Lazy get and set are amortized O(1), space O(n). A heap cleanup pop costs O(log n).

Step 8: Test boundaries

Test zero TTL, equality, refresh, repeated cleanup, clock changes, concurrent get/set, capacity eviction, and injected failures. Inject the clock rather than sleeping in tests.

High-quality sample answer

“I define CacheItem(value, expiresAt) and store items in a hash table. set converts TTL to an absolute expiry; zero means immediately expired. get checks a monotonic clock and deletes before returning a miss.

The first version uses lazy cleanup, with amortized O(1) reads and writes. For many cold keys I add a min-heap. Each heap record has a version; cleanup validates the version before deleting, so an old record cannot remove a refreshed value. Sharded locks protect the table and heap. Tests cover equality, refresh, repeated cleanup, races, and capacity eviction.”

Common mistakes

• Leaving zero TTL and equality undefined.
• Using wall-clock time for elapsed TTL.
• Letting get return an expired value until a background worker runs.
• Ignoring stale heap records after refresh.
• Treating TTL as an LRU capacity policy.
• Holding a global lock during a long cleanup.
• Testing only hits and misses, not boundary races.
• Omitting precision and complexity.

Follow-ups and how to answer

Follow-up 1: Why absolute expiry?

It gives one comparison rule and lets cleanup order entries by expiry. Refresh replaces expiresAt.

Follow-up 2: What if the wall clock moves backward?

Use a monotonic clock for elapsed time. A persistent or distributed cache needs a documented time basis.

Follow-up 3: No background thread, but many cold keys?

Perform bounded cleanup during reads or writes, such as a fixed number of heap pops per operation, and accept bounded deletion delay.

Follow-up 4: How do you keep heap and table consistent?

Use one lock or atomic operation and a version on heap records. Delete only when the version still matches.

Follow-up 5: What happens at capacity?

Remove expired entries first, then apply the documented eviction policy to live entries and track the reason.

Follow-up 6: How do multiple processes share it?

An in-memory cache is single-process. Cross-process use requires an external or distributed store with atomic TTL, clock, and failure semantics.