Time Based Key-Value Store — Binary Search on Timestamps

# Python — binary search variant
from collections import defaultdict
import bisect
class TimeMap:
    def __init__(self): self.store = defaultdict(list)
    def set(self, key, value, timestamp):
        self.store[key].append((timestamp, value))
    def get(self, key, timestamp):
        if key not in self.store: return ""
        lst = self.store[key]
        # Find rightmost timestamp <= given timestamp
        lo, hi = 0, len(lst)-1
        ans = ""
        while lo <= hi:
            mid = (lo+hi)//2
            if lst[mid][0] <= timestamp:
                ans = lst[mid][1]; lo = mid+1
            else: hi = mid-1
        return ans

// Java
class TimeMap {
    Map<String,List<int[]>> store=new HashMap<>();
    Map<String,List<String>> vals=new HashMap<>();
    public void set(String key,String val,int t) {
        store.computeIfAbsent(key,k->new ArrayList<>()).add(new int[]{t});
        vals.computeIfAbsent(key,k->new ArrayList<>()).add(val);
    }
    public String get(String key,int t) {
        if(!store.containsKey(key)) return "";
        List<int[]> ts=store.get(key); int lo=0,hi=ts.size()-1,idx=-1;
        while(lo<=hi){int mid=(lo+hi)/2;if(ts.get(mid)[0]<=t){idx=mid;lo=mid+1;}else hi=mid-1;}
        return idx==-1?"":vals.get(key).get(idx);
    }
}