Time Based Key-Value Store

1. Problem & Core Objective

Design a key-value store that keeps multiple values per key, each stamped with a time, and can retrieve the value that was current at any past moment.

set(key, value, timestamp)      // store
get(key, timestamp)             // the value with the LARGEST timestamp <= timestamp,
                                // or "" if none exists

set("foo","bar",1);  get("foo",1)  → "bar"
                     get("foo",3)  → "bar"    (nothing newer than 1 yet)
set("foo","bar2",4); get("foo",4)  → "bar2"
                     get("foo",5)  → "bar2"

Constraints: 1 <= key.length, value.length <= 100 · 1 <= timestamp <= 10^7 · up to 2 × 10^5 calls · all set calls for a key arrive with strictly increasing timestamps

What's actually being tested: recognizing that "largest timestamp ≤ query" is a floor query, which is a boundary binary search — not an exact match. The strictly-increasing guarantee is what makes each key's history already sorted, so no sorting is ever needed.

2. First-Principles Thought Process

Read the guarantee

"All the timestamps of set are strictly increasing."

That single line means each key's list of (timestamp, value) pairs is already sorted by timestamp — appending keeps it sorted, and you never re-sort.

Without it you'd need a TreeMap per key or a sort on every get.

The query is a floor, not a match

get("foo", 3) doesn't ask "what was set at time 3" — nothing was. It asks for the newest value at or before time 3.

That's a floor query: the largest key ≤ the target. In binary search terms it's a boundary — you're looking for where the timestamps stop being ≤ the query.

The structure

• Map<String, List<(timestamp, value)>> — a hash map for O(1) key lookup, and a list per key kept in insertion order.
• set is O(1) amortized: append.
• get is O(log n) over that key's list.

The hash map and the binary search do different jobs — one finds the key, the other finds the moment. Both are needed, and saying so shows you've separated the two dimensions.

The "remember the candidate" idiom

When list[mid].timestamp <= query, mid is a valid answer — but a later one might be better. So record it and keep searching right:

if (stamp <= query) { best = value; lo = mid + 1; }   // candidate — try for newer
else                { hi = mid - 1; }                  // too late — go earlier

That's the floor-query shape, and it differs from exact-match search in exactly that one line.

3. Solution Paths

Approach 1 — Linear scan backwards (brute force)

class TimeMap {
    private final Map<String, List<Object[]>> store = new HashMap<>();

    public void set(String key, String value, int timestamp) {
        store.computeIfAbsent(key, k -> new ArrayList<>()).add(new Object[]{timestamp, value});
    }

    public String get(String key, int timestamp) {
        List<Object[]> list = store.getOrDefault(key, List.of());
        for (int i = list.size() - 1; i >= 0; i--) {              // newest first
            if ((int) list.get(i)[0] <= timestamp) return (String) list.get(i)[1];
        }
        return "";
    }
}

Walk backwards from the newest entry; the first one at or before the query is the answer.

• Time set O(1), get O(n) in that key's history · Space O(n)

Counter-questions on this approach

⭐ "The list is already sorted. What does scanning throw away?"

The ability to halve. Because timestamps arrive strictly increasing, the list is sorted by construction — so a comparison at the midpoint rules out an entire half. Scanning backwards treats it as an unordered log.

"Why scan backwards rather than forwards?"

Because the answer is the newest qualifying entry, and going backwards I can return on the first hit. Forwards I'd have to scan the whole list to be sure nothing newer qualified. It's the right instinct for a linear scan — it just doesn't fix the complexity.

"How bad is it?"

With 2 × 10^5 calls, an adversary can put nearly all of them on one key: 10^5 sets then 10^5 gets, each scanning 10^5 entries → 10^10 operations. Not borderline.

Approach 2 — Binary search per key (optimal)

class TimeMap {
    private final Map<String, List<int[]>>  times  = new HashMap<>();   // key -> timestamps
    private final Map<String, List<String>> values = new HashMap<>();   // key -> values

    public void set(String key, String value, int timestamp) {
        times.computeIfAbsent(key,  k -> new ArrayList<>()).add(new int[]{timestamp});
        values.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
    }

    public String get(String key, int timestamp) {
        List<int[]>  ts = times.get(key);
        List<String> vs = values.get(key);
        if (ts == null) return "";

        String best = "";
        int lo = 0, hi = ts.size() - 1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (ts.get(mid)[0] <= timestamp) {
                best = vs.get(mid);      // a candidate — remember it
                lo = mid + 1;            // ...but look for a newer one
            } else {
                hi = mid - 1;            // too late — go earlier
            }
        }
        return best;
    }
}

(Two parallel lists keep the timestamps in a primitive-friendly structure; a single list of small records is equally fine and reads better — see §5.)

Trace — key has timestamps [1, 5, 10, 20] with values v1, v5, v10, v20; query t = 14:

Note step 3: the algorithm tried for something newer, found 20 was too late, and fell back on the candidate it had already recorded. That's the floor-query pattern working.

• Time set O(1), get O(log n) · Space O(n)

Counter-questions on this approach

⭐ "Why record best inside the loop instead of returning when you find a match?"

Because this isn't an exact-match search. When stamp <= timestamp, that entry is a valid answer — but a later entry might also qualify and be better, since I want the largest timestamp ≤ the query. So I record it as the best so far and keep searching right. Returning immediately would give an arbitrary qualifying entry, not the newest.

⭐ "Why is the list sorted? You never sort it."

The problem guarantees set calls for a key arrive with strictly increasing timestamps, so appending preserves order. That's the constraint doing the work — without it I'd need a TreeMap<Integer, String> per key, paying O(log n) on set as well as get.

"What if the key has never been set?"

times.get(key) returns null and I return "". Note I use get plus a null check rather than getOrDefault(key, List.of()) — either works, but with two parallel maps a single null check is clearer than two defaults.

"What's the complexity across all calls?"

O(1) per set and O(log n) per get, where n is that one key's history — not the total number of entries. With 2 × 10^5 calls that's at most about 18 comparisons per get.

"Could you return the timestamp too, not just the value?"

Yes — record ts.get(mid)[0] alongside best. It's free, since you're already at that entry. Worth mentioning because a real cache would want to know how stale the value is.

Approach 3 — TreeMap per key

class TimeMap {
    private final Map<String, TreeMap<Integer, String>> store = new HashMap<>();

    public void set(String key, String value, int timestamp) {
        store.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
    }

    public String get(String key, int timestamp) {
        TreeMap<Integer, String> tm = store.get(key);
        if (tm == null) return "";
        Map.Entry<Integer, String> e = tm.floorEntry(timestamp);    // the query, literally
        return e == null ? "" : e.getValue();
    }
}

TreeMap.floorEntry is the floor query, built in.

• Time set O(log n), get O(log n) · Space O(n)

Counter-questions on this approach

⭐ "This is three lines. Why would you ever write the binary search by hand?"

Because the interview is testing whether I can implement a floor query, and floorEntry hides exactly the thing being assessed. In production I'd use the TreeMap — it's clearer and handles unordered inserts for free.

It's also slightly worse here: set becomes O(log n) instead of O(1), because a red-black tree has to maintain order on every insert — order the problem already guarantees. I'd state both, write the binary search, and mention this as the production answer.

"When would the TreeMap genuinely be better?"

The moment the strictly-increasing guarantee disappears. With out-of-order set calls, the list approach needs insertion into the middle at O(n) or a re-sort; the TreeMap handles it at O(log n) with no code change. That's the §7 follow-up.

"Why floorEntry rather than floorKey?"

floorKey returns just the timestamp, so I'd need a second lookup to get the value. floorEntry returns both in one operation. See 02 §3.

Comparison

4. Why the Optimal Wins

Against the scan: the history is sorted by construction, so a midpoint comparison discards half of it. O(n) → O(log n) per get, and with 10^5 gets against a 10^5-entry history that's 10^10 versus 2 × 10^6.

Against the TreeMap: the same get complexity, but set stays O(1) because we exploit the increasing-timestamp guarantee rather than re-establishing order the input already has. Paying O(log n) on insert to maintain an order you were given for free is paying twice.

The framing worth keeping:

"Newest value at or before time T" is a floor query, and a floor query is a boundary binary search — record the candidate, keep going right.

The same shape answers "largest element ≤ x", "last version before a release", and range-start lookups in interval problems.

5. Java Prerequisites

Floor query by hand

if (stamp <= query) { best = value; lo = mid + 1; }   // candidate; try for a later one
else                { hi = mid - 1; }

The "remember and keep going" line is what distinguishes a floor query from exact match.

TreeMap navigation

tm.floorEntry(x);      // greatest entry with key <= x   (null if none)
tm.ceilingEntry(x);    // smallest entry with key >= x
tm.lowerEntry(x);      // strictly <
tm.higherEntry(x);     // strictly >

floor goes down, ceiling goes up; lower/higher are the strict versions.

Grouping with computeIfAbsent

store.computeIfAbsent(key, k -> new ArrayList<>()).add(entry);

Creates the list on first use and returns it either way, so the .add chains directly. See 02 §1.3.

A cleaner entry type. Parallel lists work but are easy to desynchronize. A record reads better:

record Stamped(int time, String value) {}
Map<String, List<Stamped>> store = new HashMap<>();

6. Interview Communication Guide

Clarifying questions: Are set timestamps strictly increasing per key (yes — this is the key guarantee)? Can two values share a timestamp (no, given "strictly")? What should get return for an unknown key or a query before the first set ("")?

The pitch

"Two dimensions here. Finding the key is a hash map lookup, O(1). Finding the right moment within that key's history is the interesting part.

get isn't an exact-match query — get(\"foo\", 3) asks for the newest value at or before time 3, even if nothing was set at 3. That's a floor query.

The problem guarantees set timestamps arrive strictly increasing per key, so each key's history is already sorted just by appending. No sorting needed, and set stays O(1).

For get I binary search that list. The detail that makes it a floor query rather than an exact match: when the midpoint's timestamp is ≤ my query, that's a valid answer, but a later one might be better — so I record it and keep searching right. If nothing newer qualifies, I fall back on the recorded candidate.

O(1) set, O(log n) get, O(n) space.

In production I'd use a TreeMap per key and call floorEntry, which is literally this query built in. But that hides the mechanic being tested, and it makes set O(log n) to maintain an order the input already guarantees."

Edge cases to volunteer:

The "query before the first set" case is the one to name — it's the only path where the loop finds no candidate at all, and it's what justifies initializing best to "" rather than to the first element.

7. Follow-Up Questions — Modified Constraints

⭐ "What if set calls arrived out of order?"

The list is no longer sorted by appending, so binary search breaks. Options: insert at the correct position — O(n) per set due to shifting — or switch to a TreeMap per key, which gives O(log n) for both operations with no code change. This is exactly where the TreeMap earns its keep, and it's why I'd mention it even while writing the binary search.

"Support deleting a key's value at a given time."

Store a tombstone — a sentinel value marking deletion — as a normal timestamped entry. get then returns "" if the floor entry is a tombstone. This is how log-structured stores handle deletes: nothing is removed, a newer record supersedes it.

"Return all values in a time range [t1, t2]."

Binary search for the lower and upper boundaries and return the slice between — O(log n + k) for k results. With a TreeMap it's subMap(t1, true, t2, true) directly.

"What if the history per key grew unbounded?"

Two directions. Compaction: drop entries older than a retention window, which keeps get fast and bounds memory. Tiering: keep recent entries in memory and older ones on disk, binary searching the in-memory portion first. That's roughly what an LSM-tree does.

"Make it thread-safe."

ConcurrentHashMap for the outer map handles concurrent keys. Within a key, appends and binary searches race — a CopyOnWriteArrayList makes reads lock-free at the cost of expensive writes, which suits read-heavy loads. Alternatively lock per key, which keeps writes cheap and contention localized.

"What if you needed the value at time T across all keys — a global snapshot?"

The per-key structure doesn't answer this efficiently; you'd run the floor query on every key, O(k log n) for k keys. For frequent snapshots you'd maintain a global version counter and index by it — essentially MVCC, the mechanism real databases use for consistent reads.