Problem 40.3 · Designing Data StructuresMedium

Time Based Key-Value Store

PatternCombine Structures to Design Binary Search on an Index

What it teaches: Append-only versions per key plus binary search for the latest version at a time.

Practise it on judges as “Time Based Key-Value Store”.

In plain words

Imagine a notebook where, for each name, you write down a new value with the time you wrote it. Later someone asks "what was foo at time 3?" You want the last entry written at or before time 3. Because the times for each name only go up, the list is already sorted, so you can binary search it instead of reading every line.

Return the value with the largest timestamp ≤ the asked time, or "" if there is none. Example: set(foo, bar, 1), get(foo, 1), get(foo, 3), set(foo, bar2, 4), get(foo, 4), get(foo, 5) → bar, bar, bar2, bar2.

The problem

Design TimeMap with set(key, value, timestamp) and get(key, timestamp) returning the value with the largest timestamp ≤ the given one, or "". Timestamps for set are strictly increasing.

Example 1

Input: set(foo, bar, 1), get(foo, 1), get(foo, 3), set(foo, bar2, 4), get(foo, 4), get(foo, 5)
Output: bar, bar, bar2, bar2

Constraints

Up to 2 × 10⁵ calls

Pattern clues in the wording

→ Versioned values
→ Latest value at or before a time

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

TimeMap · starter

import java.util.*;

class TimeMap {
    public TimeMap() {}
    public void set(String key, String value, int timestamp) {}
    public String get(String key, int timestamp) { return ""; }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["TimeMap","set","get","get","set","get","get"] args = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]	[null,null,"bar","bar",null,"bar2","bar2"]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Map of lists + binary search · O(1) set, O(log n) get

Map of lists + binary search

Time O(1) set, O(log n) get Space O(total sets)

key → ArrayList of (time, value). get finds the rightmost time ≤ t.

▶ Dry run: Binary search for the last time ≤ tset(foo, bar, 1), get(foo, 1), get(foo, 3), set(foo, bar2, 4), get(foo, 4), get(foo, 5)

values[foo](list)

bar

Step 1/5set(foo, bar, 1): append time 1 to foo's times list and bar to its values list.

Approach 1

import java.util.*;

class TimeMap {
    private final Map<String, List<Integer>> times = new HashMap<>();
    private final Map<String, List<String>> values = new HashMap<>();

    public TimeMap() {}

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

    public String get(String key, int timestamp) {
        List<Integer> t = times.get(key);
        if (t == null) return "";
        int lo = 0, hi = t.size();                 // first index with time > timestamp
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (t.get(mid) <= timestamp) lo = mid + 1; else hi = mid;
        }
        return lo == 0 ? "" : values.get(key).get(lo - 1);
    }
}

Verdict: No TreeMap overhead.

Before you submit

Edge cases and common mistakes

Test these inputs

Query before the first set ("")
Unknown key

Mistakes people make

Linear scan of all versions on each get.

Interview

Follow-up questions

What if sets could arrive out of order?

Command Palette

The problem

Approaches

Map of lists + binary search

Edge cases and common mistakes

Follow-up questions

Related problems