Time Based Key-Value Store

mediumAmazon-tagged: Design-style coding50 stepsJava · Python · C++

Store values per key with timestamps; get(key, t) returns the value with the largest timestamp ≤ t. Timestamps arrive in increasing order, so each key's list is already sorted: binary search it.

▶ Watch the animated trace

Traced input: set(foo, bar, 1), get(foo, 1), get(foo, 3), set(foo, bar2, 4), get(foo, 4), get(foo, 5) → [null, null, "bar", "bar", null, "bar2", "bar2"]. Original problem: neetcode.io/problems/time-based-key-value-store

Complexity

BestO(1)

AverageO(log n)

WorstO(log n)

SpaceO(n)

set is O(1) (append); get is a binary search.

Key idea

Map each key to a list of (timestamp, value) pairs.
Strictly increasing timestamps keep each list sorted for free.
get = find the last timestamp ≤ t (an upper-bound search, minus one).
TreeMap.floorEntry is a one-line alternative.

Common mistakes

Returning a value with a timestamp greater than t.
Linear scans make get O(n).

Solution

Java

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

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

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

Python

class TimeMap:
    def __init__(self):
        self.times = defaultdict(list)
        self.values = defaultdict(list)

    def set(self, key: str, value: str, timestamp: int) -> None:
        self.times[key].append(timestamp)
        self.values[key].append(value)

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.times:
            return ""
        i = bisect.bisect_right(self.times[key], timestamp)
        return self.values[key][i - 1] if i else ""

C++

class TimeMap {
    unordered_map<string, vector<pair<int, string>>> data;

public:
    void set(string key, string value, int timestamp) {
        data[key].push_back({timestamp, value});
    }

    string get(string key, int timestamp) {
        auto it = data.find(key);
        if (it == data.end()) {
            return "";
        }
        auto& h = it->second;
        int lo = 0, hi = h.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (h[mid].first <= timestamp) lo = mid + 1;
            else hi = mid;
        }
        return lo == 0 ? "" : h[lo - 1].second;
    }
};

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Before any timestamp No timestamp ≤ 2.	`set(a, x, 5), get(a, 2)`	`[null, null, ""]`
Unknown key Return the empty string.	`get(zzz, 1)`	`[null, ""]`