Design an in-memory key-value store where each key can expire after a time-to-live (TTL). There is no clock: every call passes the current time now as an integer, and across all calls that take now, it never decreases.
Implement the class TTLStore() with:
set(key, value, now, ttl=None) stores value under key and returns None. If ttl is None the key never expires. Otherwise ttl is a positive integer and the key is live for times t with now <= t < now + ttl, so at exactly now + ttl it is gone. Setting an existing key replaces both its value and its expiry.get(key, now) returns the value if key is live at now, otherwise None.delete(key, now) removes key and returns True if it was live, or False if there was nothing live to remove.1 1 None
s = TTLStore()
s.set("a", 1, 10, 5)
print(s.get("a", 10))
print(s.get("a", 14))
print(s.get("a", 15))Design a key-value store whose keys expire after a time-to-live, with time passed in. Then renew keys and count live ones efficiently, look up past values, and back up and restore the store.
Also known as: Key-value store with TTL, Point-in-time key-value store, Expiring key-value store
Time-based state (expiry, TTL, snapshots) shows up in 10.4% of the 1,447 coding interview reports we studied, at 9 companies. Values that expire, versions you can read back, or queries of the form "what was true at time t". Follow-ups often allow calls to arrive out of time order.
Reported at: OpenAI, Anthropic, Databricks, Citadel, Snowflake, Palantir, Perplexity, Waymo, Zip.
This is an original practice problem written by AceOffer to train the pattern. It is not a question any company asked.
Follow-ups candidates reported on questions with this pattern, in our words. Parts marked “from reports” below are built on them.
Design an in-memory key-value store where each key can expire after a time-to-live (TTL). There is no clock: every call passes the current time now as an integer, and across all calls that take now, it never decreases.
Implement the class TTLStore() with:
set(key, value, now, ttl=None) stores value under key and returns None. If ttl is None the key never expires. Otherwise ttl is a positive integer and the key is live for times t with now <= t < now + ttl, so at exactly now + ttl it is gone. Setting an existing key replaces both its value and its expiry.get(key, now) returns the value if key is live at now, otherwise None.delete(key, now) removes key and returns True if it was live, or False if there was nothing live to remove.Add:
renew(key, now): if key is live at now, its expiry becomes now + ttl, using the ttl from the last set of that key, and the call returns True. A live key without a ttl stays without one and also returns True. A missing or expired key returns False and nothing changes.count(now) returns how many keys are live at time now. A key set twice counts once; expired and deleted keys do not count.Tests only check the numbers, but avoid scanning every key on each call. Because now never goes backwards, a key that has expired can be thrown away once and for all.
Add get_at(key, timestamp), which returns the value key held at timestamp, or None if it held no live value then. timestamp can be any integer, including times before the latest now.
A value set at time s is the answer from s until the first of: its expiry (moved later by any renew), the next set of the same key, or a delete of that key. If several calls happen at the same time, get_at sees the state after the last of them. get_at changes nothing.
Add:
backup(now) saves a copy of every key live at now: its value and its remaining ttl, expiry - now (or None for a key without a ttl). Returns None. Several backups can exist; they are kept after a restore.restore(now, backup_time) picks the latest backup taken at or before backup_time and makes the store match it as of now. Keys not in that backup are deleted. Each saved key gets its saved value, and its saved remaining ttl now counts from now. After the restore, a restored key behaves as if it had just been set at now with that remaining ttl, so renew and get_at follow the usual rules. Returns True, or False with nothing changed if no backup was taken at or before backup_time.Open this page on a laptop or desktop to write and run your code against the tests in the browser.
Spoilers: try each part before reading its walkthrough.
Store each key with its value and an absolute expiry time, now + ttl, rather than the ttl itself. A key is then live exactly when now < expiry, which is a single comparison in get, and a key set without a ttl can use infinity as its expiry so the same test works. Setting a key again simply replaces the stored pair, which gives the new value a fresh expiry. delete must report whether something live was removed, so it has to treat an expired key as absent. In the reference solution all three methods first run a cleanup step that drops keys whose expiry has passed; that step exists for Part 2, but it also means a stale key is never returned. Each operation is a dict lookup plus that amortized cleanup.
Renewing and counting both rely on the same structure. Push (expiry, version, key) onto a min-heap whenever a key gets a finite expiry, from a set or a renew. Because now never goes backwards, any key whose expiry is at or before now will stay expired, so a cleanup step pops it from the heap and deletes it from the dict for good; after cleanup, count is just the size of the dict. renew first runs that cleanup, so an expired key is already gone and the call returns False. For a live key it stores the new expiry and pushes a fresh heap entry with a new version. The old entry stays in the heap, and when it is popped the version check makes it a no-op. Every call is O(log n) amortized.
For lookups in the past, keep a history per key: a list of [start, end, value] intervals in the order they were set, plus a parallel list of starts. A new set at time p shortens the previous interval so it ends at p, a delete at time d ends it at d, and a renew moves the end of the current interval later. Since calls arrive in time order, starts are sorted, so get_at uses bisect_right on the starts to find the last interval that began at or before the timestamp, then checks that the timestamp falls before its end. Using bisect_right means that when two sets share a time, the later one wins. Lookups are O(log h) for h values of that key.
A backup is a plain copy of the live keys taken after cleanup, storing each value with its remaining ttl, expiry - now, or None for keys that never expire. Backups go into a list in time order, so restore can find the latest one at or before backup_time with a bisect on their times. The key design choice is to restore through the public operations instead of editing internals: every live key missing from the backup is removed with delete(key, now), and every saved key is written back with set(key, value, now, remaining). That single decision keeps the heap, the live count and the per-key history correct with no extra code, and it is why a restored key renews with its remaining ttl. Backup costs O(n) and restore O(n log n).
Store the absolute expiry time (now + ttl) with the value. Then a key is live when now < expiry, and a key without a ttl can use infinity.
Keep a min-heap of (expiry, version, key). Pop while the top has expired and drop the key only if its version still matches; set and renew push a fresh version instead of editing the heap.
Per key, keep a list of [start, end, value] in start order. A new set or a delete shortens the last interval and a renew lengthens it. Look up a time with bisect_right on the starts.
Store each backup as (time, dict of key to (value, remaining ttl)). Restore can then reuse delete and set at the restore time, which keeps the heap, the count and the history consistent for free.
set, renew and delete are O(log n) for the heap; get and count are amortized O(log n) because each heap entry is popped at most once. get_at is O(log h) for h stored values of that key. backup is O(n) for n live keys and restore is O(n log n) through set and delete. Memory is O(number of set and renew calls) plus every backup.
The company guides collect the questions candidates report, with every part, the follow-ups interviewers added, and how often each one comes up.
Browse the interview guides