Time Based Key-Value Store

Problem Statement

Design a store supporting set(key, value, timestamp) and get(key, timestamp), where get returns the value set at the largest timestamp <= the query timestamp (or "" if none). Timestamps for a key are strictly increasing.

Example

set("foo","bar",1); get("foo",1) -> "bar"; get("foo",3) -> "bar"

Approach

Store a list of (timestamp, value) per key; because sets arrive with increasing timestamps the list is already sorted. For get, binary-search the largest timestamp <= query and return its value.

Complexity

• Time: O(1) set, O(log n) get
• Space: O(total entries)

Solution Code

Python

class TimeMap:
    def __init__(self):
        self.store = {}
    def set(self, key, value, timestamp):
        self.store.setdefault(key, []).append((timestamp, value))
    def get(self, key, timestamp):
        arr = self.store.get(key, [])
        lo, hi, res = 0, len(arr) - 1, ""
        while lo <= hi:
            mid = (lo + hi) // 2
            if arr[mid][0] <= timestamp:
                res = arr[mid][1]
                lo = mid + 1
            else:
                hi = mid - 1
        return res

Java

class TimeMap {
    Map<String, List<int[]>> store = new HashMap<>();
    Map<String, List<String>> vals = new HashMap<>();
    void set(String key, String value, int timestamp) {
        store.computeIfAbsent(key, z -> new ArrayList<>()).add(new int[]{timestamp});
        vals.computeIfAbsent(key, z -> new ArrayList<>()).add(value);
    }
    String get(String key, int timestamp) {
        List<int[]> arr = store.getOrDefault(key, new ArrayList<>());
        int lo = 0, hi = arr.size() - 1, idx = -1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (arr.get(mid)[0] <= timestamp) { idx = mid; lo = mid + 1; }
            else hi = mid - 1;
        }
        return idx == -1 ? "" : vals.get(key).get(idx);
    }
}

C++

class TimeMap {
    unordered_map<string, vector<pair<int,string>>> store;
public:
    void set(string key, string value, int timestamp) {
        store[key].push_back({timestamp, value});
    }
    string get(string key, int timestamp) {
        auto& arr = store[key];
        int lo = 0, hi = (int)arr.size() - 1; string res = "";
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid].first <= timestamp) { res = arr[mid].second; lo = mid + 1; }
            else hi = mid - 1;
        }
        return res;
    }
};

Key Takeaways

• Increasing timestamps keep each key’s list sorted — no sorting needed.
• The get is an upper-bound-style search: largest timestamp <= query.
• Reference: LeetCode 981 (Time Based Key-Value Store).