A feature-flag service keys each flag by name and stamps every publish with a write time. Rollbacks call get-as-of: given a name and a timestamp t, return the value that was live then, not the current one. The first version nested a scan of that flag’s history on every get, tracking the latest stamp still <= t. A dozen flags in staging returned before the page painted. A production tenant with years of publishes was still walking that history when the request timed out.

Time-Based Key-Value Store asks for the value at the latest stamp still <= t. A hash table already gives get-by-name. A scan of that name’s versions uses that and still pays linear time in the history. The versions are ordered by stamp — that is the license for binary search, not decoration.

This is an interview writeup, not a hashing or binary-search lecture. The hash-table post owns buckets and collisions. The binary-search post owns the invariant, lower/upper bound, and miss encoding. Here we only care about appending stamps per key, then probing the latest stamp still legal at t.

The problem

Implement a store with two operations. set(key, value, timestamp) records that key held value starting at timestamp. get(key, timestamp) returns the value whose timestamp is the largest still <= the query, or "" if no such stamp exists. The usual prompt guarantees timestamps for a given key are strictly increasing, so set never inserts in the middle of that key’s history.

set("checkout.tax", "0.08", 10)
set("feature.dark-mode", "off", 20)
set("checkout.tax", "0.09", 40)

get("checkout.tax", 10)         →  "0.08"
get("checkout.tax", 25)         →  "0.08"
get("checkout.tax", 40)         →  "0.09"
get("checkout.tax", 5)          →  ""
get("shipping.fee", 40)         →  ""

Note: get is as-of, not exact-match. A query between two stamps of the same key returns the earlier value. A query before every stamp, or on a key never set, returns "" — not the next future value.

A linear walk of history is the honest brute force

Hash the name to a list if you want; the brute is still get walking every matching stamp and keeping the latest one <= t. A global list of triples is the same walk without even hashing. Correct. Linear in that key’s history — or in every write, if you skipped the map.

class TimeMapScan {
    record Entry(int timestamp, String value) {}

    Map<String, List<Entry>> store = new HashMap<>();

    void set(String key, String value, int timestamp) {
        List<Entry> history = store.get(key);
        if (history == null) {
            history = new ArrayList<>();
            store.put(key, history);
        }
        history.add(new Entry(timestamp, value));
    }

    String get(String key, int timestamp) {
        List<Entry> history = store.get(key);
        if (history == null) {
            return "";
        }
        String answer = "";
        for (Entry e : history) {
            if (e.timestamp() <= timestamp) {
                answer = e.value();
            }
        }
        return answer;
    }
}

At a dozen publishes this is a rounding error. At years of config history you paid a full walk for a question a sorted stamp list answers in a handful of probes: what is the latest stamp still <= t?

Hash the key, append, then probe the floor

Map<String, List<Entry>>. set hashes the key and appends, because stamps only move forward. get is a floor search on that list: the rightmost stamp still <= t. The binary search post already owns that halt; we do not re-derive it here.

  • If mid’s stamp is <= t, it is legal; record it and look right for a later legal stamp.
  • If mid’s stamp is > t, it is future; look left.
  • An empty pick — missing key, or every stamp after t — is "".

Walk a short session. Each key keeps its own ordered list.

set("checkout.tax", "0.08", 10)
set("feature.dark-mode", "off", 20)
set("checkout.tax", "0.09", 40)
set("feature.dark-mode", "on", 55)

store:
  checkout.tax       [(10, "0.08"), (40, "0.09")]
  feature.dark-mode  [(20, "off"),  (55, "on")]

get("checkout.tax", 10)          →  "0.08"   exact stamp
get("checkout.tax", 25)          →  "0.08"   40 is future; floor is 10
get("checkout.tax", 40)          →  "0.09"
get("checkout.tax", 5)           →  ""       all stamps after 5
get("shipping.fee", 40)          →  ""       missing key
get("feature.dark-mode", 54)     →  "off"

The Java is that class. set appends. get probes the floor and returns "" when the pick never moved.

class TimeMap {
    record Entry(int timestamp, String value) {}

    Map<String, List<Entry>> store = new HashMap<>();

    void set(String key, String value, int timestamp) {
        List<Entry> history = store.get(key);
        if (history == null) {
            history = new ArrayList<>();
            store.put(key, history);
        }
        history.add(new Entry(timestamp, value));
    }

    String get(String key, int timestamp) {
        List<Entry> history = store.get(key);
        if (history == null) {
            return "";
        }
        int lo = 0;
        int hi = history.size() - 1;
        int pick = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (history.get(mid).timestamp() <= timestamp) {
                pick = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return pick < 0 ? "" : history.get(pick).value();
    }
}

Time is expected O(1) amortized per set — hash the key, append. get is O(log n) on that key’s history. Space is O(total sets). Do not re-lecture hash buckets or the binary-search invariant at the whiteboard unless they ask.

Note: Do not return the next future value. If the key is missing, or every stamp is after t, return "". The increasing guarantee is why set appends; if stamps could arrive out of order, you would sort first or keep a TreeMap before you probe.

What interviewers usually poke next

  • TreeMap per key. TreeMap<Integer, String> and floorEntry(t). Works even if stamps arrive out of order. set is no longer an append; you paid O(log n) on write too.
  • Unsorted timestamps. The list is no longer a sorted range. Sort on get, insert in order, or switch to TreeMap. Binary search on an unsorted history is a lie.
  • Same timestamp twice. The usual prompt forbids it. If they allow it, ask which value wins — last write is the usual production answer; do not invent a merge.
  • Parallel int[] timestamps. Same floor search, values in a second list. Arrays.binarySearch encodes a miss as -(insertionPoint) - 1; that encoding already lives on the algorithms post.

You are done with this problem when you can say, out loud, why walking that key’s history is correct, why strictly increasing stamps license an append plus a floor probe, and why a miss returns empty instead of the next future value.