Implement an In-Memory Key-Value Cache With Per-Entry Time Limits

Implement a time-limited cache: an in-memory key-value store in which every entry carries its own time limit. Each write supplies a key, a value and a duration. Once the duration has elapsed, the entry must behave as if it had never been written. Assume the cache exposes these operations: - `set(key, value, duration)` stores `value` under `key` for `duration` time units. It returns `true` if the key already had an unexpired entry and `false` otherwise. Writing to a key that already has an unexpired entry replaces both the value and the time limit. - `get(key)` returns the value if the key has an unexpired entry, and a miss indicator otherwise. - `count()` returns the number of keys that currently have unexpired entries. ```hint Decide when expiry happens An entry can be treated as gone the moment its time passes, or physically removed later. Decide which operations need which, and what that costs. ``` ```hint Make time controllable Think about how you would test expiry at an exact moment without your tests sleeping. ``` ### Constraints and Clarifications - Durations are positive. - Assume an entry written at time `t` with duration `d` is visible at every time before `t + d`, and expired from `t + d` onward. - Expired entries must not be returned by `get` or counted by `count`, even if they are still in memory. ### Clarifying Questions - What unit are durations in, and which clock should the cache use? - What should `get` return on a miss: a sentinel such as `-1`, a null value, or an error? - Does a successful `get` extend the entry's time limit, or is the limit fixed when the entry is written? - Is there a maximum number of entries, and if so, what is evicted when it is reached? - Will several threads use the cache at the same time? ### What a Strong Answer Covers - Correct visibility: an expired entry is never returned or counted, including at the exact expiry moment - Memory reclaimed for expired entries, not only hidden - Overwrite semantics, where the new time limit replaces the old one - The time complexity of each operation and of cleanup - An injectable clock and tests at the expiry boundary ### Follow-up Questions - Add a maximum capacity with least-recently-used eviction. How do the data structures change? - Make the cache safe for concurrent readers and writers. Where is the contention? - Millions of keys expire at the same moment. How do you avoid a long pause? - How would the design change if the cache had to be shared by several servers?