Time Based Key-Value Store — Binary Search on Timestamps

from collections import defaultdict
import bisect

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

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

    def get(self, key: str, timestamp: int) -> str:
        arr = self.store[key]
        idx = bisect.bisect_right(arr, (timestamp, chr(127)))
        if idx == 0:
            return ""
        return arr[idx - 1][1]

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, res = "";
        while (lo <= hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid][0] <= timestamp) { res = arr[mid][1]; lo = mid + 1; }
            else hi = mid - 1;
        }
        return res;
    }
}

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

#include <unordered_map>
#include <vector>
#include <string>
using namespace std;
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& v = store[key];
        int lo = 0, hi = (int)v.size() - 1; string res = "";
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (v[mid].first <= timestamp) { res = v[mid].second; lo = mid + 1; }
            else hi = mid - 1;
        }
        return res;
    }
};

/* C: sorted array of {timestamp, value_index} pairs per key */
/* Binary search with standard bsearch or manual lo/hi loop */