Implement an in-memory key-value store with per-key TTL expiration and tests

In a phone screen, implement an in-memory key-value store in which every entry expires after its own time-to-live (TTL). Implement the usual operations, explain your design and its trade-offs as you go, and finish by writing test cases and running them.

The interviewer evaluates more than whether the code runs: how you clarify the requirements and break the problem down, whether the code is concise and direct, and whether your explanation stays coherent from the first idea to the last test.

Unless the interviewer changes it, assume this interface:

class TTLStore:
 def put(self, key: str, value: object, ttl: float) -> None: ...
 def get(self, key: str) -> object | None: ...
 def delete(self, key: str) -> bool: ...

• put stores value under key; the entry expires ttl time units after the call.
• get returns the value if the key exists and has not expired, otherwise None.
• delete removes the key and reports whether a live entry was removed.

Constraints and Clarifications

• One process, data in memory only; no persistence or replication.
• Keys are strings, values are arbitrary objects, and ttl is a positive number in the same unit as the clock you use.
• The exact behavior at the moment an entry reaches its expiry time is not specified. Define it.

Clarifying Questions

• Does put on an existing key replace its TTL as well as its value?
• Is a TTL required on every put, or can some entries live forever?
• Should get distinguish a missing key from an expired one, and can a stored value be None?
• Are other operations needed, such as counting live keys or extending a key's TTL?
• Will several threads use the store at the same time?
• Must memory held by expired entries be reclaimed even if those keys are never read again?

Part 1 — Core operations and expiry semantics

Implement put, get and delete so that an expired entry is never returned.

What This Part Should Cover

• The state stored per entry, and the exact expiry boundary
• Overwrite semantics, including what happens to the previous TTL
• The choice of time source, and why
• The time complexity of each operation

Part 2 — Removing expired entries

A key that is written once and never read again stays in memory forever if expiry is checked only inside get. Add a mechanism that removes expired entries without scanning the whole store, and explain how it interacts with overwrites and deletes.

What This Part Should Cover

• The cleanup data structure, and when cleanup runs (inside each operation, in a background thread, or both)
• Handling outdated expiry records left by overwrites and deletes
• Amortized cost, and worst-case pauses when many keys expire together
• Memory growth from outdated records, and how to bound it

Part 3 — Tests

Write test cases that show the store works, including its time-dependent behavior, and that run quickly and deterministically.

What This Part Should Cover

• How tests control time
• Boundary cases: exactly at expiry, overwrite before expiry, delete followed by reinsert, missing keys
• A test proving that cleanup frees entries that are never read