Skip to main content
DSA patterns

Time Based Key-Value Store

mediumBinary search Must-doGoogleAmazonDatadog

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 that key took on value at timestamp. For any one key, set is always called with strictly increasing timestamps.
  • get(key, timestamp) returns the value that was set for key at the largest recorded timestamp that is still ≤ the given timestamp. 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

Hint 1: Don't overwrite the old value on 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

  1. Keep two parallel arrays per key: one of timestamps, one of the matching values (both append-only, so they stay sorted automatically).
  2. On set, append the new timestamp and value to that key's two arrays.
  3. On get, binary search the key's timestamps array for the rightmost timestamp that is ≤ the target.
  4. If no timestamp qualifies (the target is earlier than everything ever set, or the key doesn't exist), return "".
  5. 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))   # bar2
RecapThe 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) per get; O(n) total space across every key's history
  • Trap: re-scanning or re-sorting a key's history on every get throws 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 set would then need to insert into the correct spot in that key's array instead of just appending — for example bisect.insort in 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 both set and get at 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. A get for a key that's still cached answers from memory with the same binary search; a get for 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.