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: ```python 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. ```hint Record what you will compare against Decide what to store at `put` time so that a later `get` can tell whether the entry is still valid with a single comparison, and decide where the current time comes from. ``` #### 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. ```hint Which key expires next? Look for a structure that can always tell you the earliest pending expiry cheaply, even as new keys keep arriving. ``` ```hint Overwrites leave traces When a key is overwritten or deleted, its old expiry is still recorded somewhere. Decide how cleanup recognizes that record as outdated instead of deleting the newer value. ``` #### 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. ```hint Do not wait for real time Tests that sleep are slow and flaky. Think about how a test could move time forward on demand. ``` #### 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 ### What a Strong Answer Covers - Clarifies overwrite, boundary, missing-versus-expired and concurrency semantics before coding - A short plan stated up front, followed by code that implements it directly with no unnecessary abstraction - Correct handling of outdated expiry records after overwrites and deletes - Complexity analysis, and at least one alternative cleanup strategy with its trade-off - A coherent narration that ties each decision to a requirement, and tests that cover the edge cases ### Follow-up Questions - Make the store safe for concurrent callers. Where do the locks go, and does a background cleanup thread change your answer? - A million keys expire in the same second. How do you keep a single `put` from pausing while all of them are removed? - Add a maximum number of entries with least-recently-used eviction alongside the TTL. How do the two mechanisms interact? - What alternatives exist to the cleanup structure you chose, such as a timing wheel or periodic random sampling of keys, and when would each one win?