Time Based Key-Value Store
Problem statement
You are building a small in-memory config store used by deployment tooling. Each key (a feature flag or a config name) can be set many times, and every change is stamped with when it happened. Given a key and a target timestamp, return the value that key held at or before that timestamp — the state a deploy tool would have seen if it had checked at that moment.
Implement a TimeMap class:
TimeMap()creates an empty store.set(key, value, timestamp)records thatkeytook onvalueattimestamp. For any one key,setis always called with strictly increasing timestamps.get(key, timestamp)returns the value that was set forkeyat the largest recorded timestamp that is still ≤ the giventimestamp. If no such value exists — the key was never set, or every timestamp recorded for it comes after the one asked for — return an empty string"".
Examples
Example 1
Input: ["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output: [null, null, "bar", "bar", null, "bar2", "bar2"]
Explanation: set("foo", "bar", 1) records bar at time 1. get("foo", 1) matches that timestamp exactly, so it returns "bar". get("foo", 3) has no entry at time 3, so it falls back to the latest entry at or before 3, which is still "bar" from time 1. set("foo", "bar2", 4) adds a second value. get("foo", 4) matches time 4 exactly ("bar2"), and get("foo", 5) has no entry at 5 so it falls back to the latest one at or before 5, which is "bar2".
Hints
set — a key may need to answer for many past moments, so keep every value it was ever given, tagged with when.Approach
Optimal: Binary search per key
Intuition
Because set for one key always arrives with a strictly larger timestamp
than the one before it, that key's history is already sorted by timestamp —
there's nothing to sort. Finding "the last timestamp that is ≤ the target" in
a sorted list is exactly what binary search does: look at the middle
timestamp, decide whether the answer could be to its left or its right, and
repeat on the half that could still hold it. That turns each get from
O(n) into O(log n), which starts to matter once a key has been set thousands
of times — say, a config value that changes on every deploy.
Steps
- Keep two parallel arrays per key: one of timestamps, one of the matching values (both append-only, so they stay sorted automatically).
- On
set, append the new timestamp and value to that key's two arrays. - On
get, binary search the key's timestamps array for the rightmost timestamp that is ≤ the target. - If no timestamp qualifies (the target is earlier than everything ever set,
or the key doesn't exist), return
"". - Otherwise return the value stored at that same position in the values array.
Dry run
Timestamps for "foo": [1, 4]. Query get("foo", 4):
| step | lo | hi | mid | ts[mid] ≤ 4? | action |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 ≤ 4, yes | remember index 0, search right half: lo = 1 |
| 2 | 1 | 1 | 1 | 4 ≤ 4, yes | remember index 1, search right half: lo = 2 |
| — | 2 | 1 | — | lo > hi, stop | answer is the last remembered index, 1 → "bar2" |
Edge cases: get with a timestamp before the key's first set finds no
qualifying index and returns "". A timestamp that exactly matches a
recorded one returns that value, not an earlier one — the binary search keeps
moving right on a tie, which is what makes it prefer the most recent match.
Complexity
Time O(log n) - per `get`, where n is how many times that key has been `set` — each query halves the range of candidate timestamps instead of scanning them one by one. `set` stays O(1) amortized, since it only appends.
Space O(n) - total, same as the brute-force version — every value ever set is still kept, just split into two parallel arrays per key instead of one list of pairs.
from bisect import bisect_right
class TimeMap:
def __init__(self):
self.timestamps: dict[str, list[int]] = {}
self.values: dict[str, list[str]] = {}
def set(self, key: str, value: str, timestamp: int) -> None:
self.timestamps.setdefault(key, []).append(timestamp)
self.values.setdefault(key, []).append(value)
def get(self, key: str, timestamp: int) -> str:
ts_list = self.timestamps.get(key)
if not ts_list:
return ""
i = bisect_right(ts_list, timestamp) - 1
return self.values[key][i] if i >= 0 else ""
if __name__ == "__main__":
tm = TimeMap()
tm.set("foo", "bar", 1)
print(tm.get("foo", 1)) # bar
print(tm.get("foo", 3)) # bar
tm.set("foo", "bar2", 4)
print(tm.get("foo", 4)) # bar2
print(tm.get("foo", 5)) # bar2RecapThe whole problem in a few lines, for the night before
- Spot it: "store multiple values per key, each tagged with a timestamp; look up the value as of some time" — a design question with a lookup twist
- Idea: append
(timestamp, value)per key (already sorted, since timestamps only increase for a key); binary search for the rightmost timestamp ≤ the query - Cost: O(1) amortized per
set(just an append), O(log n) perget; O(n) total space across every key's history - Trap: re-scanning or re-sorting a key's history on every
getthrows away the "already sorted" guarantee for nothing — binary search needs no sorting step at all here
Interview follow-ups
What if timestamps for the same key could arrive out of order?
You'd lose the "already sorted" guarantee that makes plain binary search possible. Each
setwould then need to insert into the correct spot in that key's array instead of just appending — for examplebisect.insortin Python, which costs O(n) per insert because the rest of the array has to shift, or a balanced tree keyed by timestamp, which keeps bothsetandgetat O(log n). The right trade-off depends on how often out-of-order writes actually happen.How would you support millions of keys without keeping every key's full history in memory?
Keep a small in-memory index — say, the most recently touched keys, with an LRU eviction policy — and write each key's
(timestamp, value)history to disk or a time-series store, since it's naturally append-only. Agetfor a key that's still cached answers from memory with the same binary search; agetfor a key that's been evicted reads its history back from disk and binary searches that instead, at the cost of one extra I/O.
Frequently asked questions
That's a perfectly good answer in languages that ship one — Java's TreeMap.floorKey does exactly this in a few lines. This page writes it out with a plain array and binary search because that's the version interviewers most often want to see you build yourself, and it's what to reach for in a language like Python whose standard library has no built-in balanced tree.
No. The constraints guarantee that set calls for a given key always arrive with a strictly increasing timestamp, so appending to the end of that key's list is always safe and always keeps it sorted. If that guarantee were dropped, you'd need something like bisect.insort in Python, or a genuinely sorted structure, to insert a late-arriving timestamp in the right place.
Recording a series of changes to something — a config value, a feature flag, an instance's health status — and then asking "what was it at this point in time" is the core of audit logs, deployment rollbacks and time-travel debugging. This problem is that idea reduced to its simplest form: one key, a list of timestamped values, and a "most recent at or before" lookup.
The constraints rule this out — timestamps for one key are strictly increasing — so it can't happen with valid input here. If it could, you'd have to decide the tie-breaking rule yourself (usually: the later set call wins), and keep only one entry per timestamp instead of two.