Implement an In-Memory Key-Value Cache with Expiry, Then Sketch a Redis-Like Server

Implement an in-memory key-value cache that behaves like a small subset of Redis, then spend a few minutes on how you would design a Redis-like system and where a cache like this is useful. The design portion is brief and mainly checks your knowledge of how caches are used; most of the time goes to writing working code. ### Constraints and Clarifications - Assume single-process, in-memory storage; persistence and networking belong to the design discussion, not to the code. - Keys are strings. Values can be any object unless the interviewer narrows them. - Ask before adding features: the set of operations, expiry semantics, a size limit and concurrent access are all open until confirmed. ### Clarifying Questions - Which operations are required: get, set and delete only, or also counters, existence checks and key listing? - Should keys support a time-to-live, and is expiry measured from the last write or the last read? - Is there a limit on the number of entries or on memory, and which keys go first when it is reached? - Will several threads use the cache at the same time? - How should a lookup of a missing or expired key be reported? ### Part 1 — Implement the cache Write a cache class that supports at least `set(key, value, ttl=None)`, `get(key)` and `delete(key)`, where a key written with a `ttl` stops being visible once that many seconds have passed. If the interviewer adds a capacity limit, evict entries by a policy you choose and justify. State the complexity of each operation and show how you would test expiry without waiting in real time. ```hint Two ways to forget a key An expired key can be removed when someone asks for it or proactively in the background; consider what each approach costs in time and memory, and whether you need both. ``` #### What This Part Should Cover - Correct expiry semantics, including keys that are overwritten or deleted before they expire - Data structures that keep get, set and delete fast, with complexity stated - A capacity and eviction policy if one is required, and safe behavior under concurrent access - Tests that control time instead of sleeping ### Part 2 — Sketch a Redis-like system and its uses Briefly describe how you would turn the cache into a networked service in the spirit of Redis: how clients talk to it, how commands are executed, how data survives a restart, and how it scales beyond one machine. Then describe the situations in which you would put a cache like this in front of other systems, and the problems caching introduces. ```hint Where the time goes Consider how long a command against in-memory data actually takes compared with moving bytes over the network, and what that implies for how many threads need to touch the data. ``` #### What This Part Should Cover - The request-handling and execution model, and how it makes each command atomic - Persistence options and replication, with their durability trade-offs - Common cache use cases and patterns such as cache-aside and write-through - Caching hazards: invalidation, stale reads, stampedes and hot keys ### What a Strong Answer Covers - Working, readable code delivered early, then refined - The feature set clarified before building, rather than over-engineering - Precise reasoning about time, including the expiry boundary and an injectable clock - Awareness of memory growth and of how stale bookkeeping is cleaned up - Practical judgment about when a cache helps and when it creates correctness risk ### Follow-up Questions - How would you add an atomic increment operation, and why does atomicity matter for it? - How would you approximate least-recently-used eviction cheaply when there are millions of keys? - What changes if values vary widely in size and the limit is on memory rather than on entry count? - How would you keep the cache consistent with the database it fronts when both are updated?