Time Based Key-Value Store

medium hash map binary search design

Problem

Implement a TimeMap supporting set(key, value, timestamp) and get(key, timestamp). get returns the value attached to the largest timestamp ≤ the query timestamp, or "" if no such record exists. set is called with strictly increasing timestamps for each key.

Inputset("foo","bar",1); set("foo","baz",4); get("foo",3); get("foo",4); get("foo",5)

Output"bar", "baz", "baz"

At t=3 the latest ≤ 3 is t=1 → "bar"; at t=4 the latest ≤ 4 is t=4 → "baz".

timestamps for key "foo" (comma-separated, sorted)

values

query t

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, ans = 0, len(arr) - 1, ""
        while lo <= hi:
            mid = (lo + hi) // 2
            if arr[mid][0] <= timestamp:
                ans = arr[mid][1]
                lo = mid + 1
            else:
                hi = mid - 1
        return ans

class TimeMap {
  constructor() { this.store = new Map(); }
  set(key, value, timestamp) {
    if (!this.store.has(key)) this.store.set(key, []);
    this.store.get(key).push([timestamp, value]);
  }
  get(key, timestamp) {
    const arr = this.store.get(key) || [];
    let lo = 0, hi = arr.length - 1, ans = "";
    while (lo <= hi) {
      const mid = (lo + hi) >> 1;
      if (arr[mid][0] <= timestamp) { ans = arr[mid][1]; lo = mid + 1; }
      else hi = mid - 1;
    }
    return ans;
  }
}

class TimeMap {
    Map<String, List<int[]>> tStore = new HashMap<>();
    Map<String, List<String>> vStore = new HashMap<>();
    public void set(String key, String value, int timestamp) {
        tStore.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{timestamp});
        vStore.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
    }
    public String get(String key, int timestamp) {
        List<int[]> ts = tStore.getOrDefault(key, new ArrayList<>());
        List<String> vs = vStore.getOrDefault(key, new ArrayList<>());
        int lo = 0, hi = ts.size() - 1; String ans = "";
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (ts.get(mid)[0] <= timestamp) { ans = vs.get(mid); lo = mid + 1; }
            else hi = mid - 1;
        }
        return ans;
    }
}

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 ans = "";
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (arr[mid].first <= timestamp) { ans = arr[mid].second; lo = mid + 1; }
            else hi = mid - 1;
        }
        return ans;
    }
};

Explanation

We are building a tiny database where each key remembers a history of values stamped with a time. A get(key, timestamp) must return the value from the latest moment at or before that timestamp. The clever part is that we never have to scan the whole history.

Because set is always called with increasing timestamps, the list stored for each key is automatically sorted by time. That lets get use binary search instead of a linear scan.

During the search we look at the middle entry. If its timestamp is <= timestamp, it is a valid candidate, so we save its value in ans and move right to look for an even more recent one. If it is too new, we move left. When the window closes, ans holds the best match (or "" if nothing qualified).

Example: key "foo" holds [(1,"bar"), (4,"baz")]. For get("foo", 3), the only timestamp <= 3 is 1, so we return "bar". For get("foo", 4) we can reach 4, so we return "baz".

set just appends, so it is constant time, and each get is fast because binary search only touches about log n entries.

Time: O(log n) per get, O(1) per set Space: O(n)