Time-Based Key-Value Store

class TimeMap {
    unordered_map<string, vector<pair<int, string>>> mp;
public:
    void set(string key, string value, int timestamp) {
        mp[key].push_back({timestamp, value});
    }

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

type tmEntry struct {
  timestamp int
  value     string
}

type TimeMap struct {
  mp map[string][]tmEntry
}

func Constructor() TimeMap {
  return TimeMap{mp: map[string][]tmEntry{}}
}

func (t *TimeMap) Set(key string, value string, timestamp int) {
  t.mp[key] = append(t.mp[key], tmEntry{timestamp, value})
}

func (t *TimeMap) Get(key string, timestamp int) string {
  v, ok := t.mp[key]
  if !ok {
    return ""
  }
  lo, hi, ans := 0, len(v)-1, -1
  for lo <= hi {
    m := (lo + hi) / 2
    if v[m].timestamp <= timestamp {
      ans = m
      lo = m + 1
    } else {
      hi = m - 1
    }
  }
  if ans == -1 {
    return ""
  }
  return v[ans].value
}

import bisect
from collections import defaultdict
from typing import List, Tuple

class TimeMap:
    def __init__(self):
        self.times: dict = defaultdict(list)
        self.values: dict = 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 ""
        ts = self.times[key]
        idx = bisect.bisect_right(ts, timestamp) - 1
        if idx < 0:
            return ""
        return self.values[key][idx]

var TimeMap = function() {
    this.mp = new Map();
};

TimeMap.prototype.set = function(key, value, timestamp) {
    if (!this.mp.has(key)) this.mp.set(key, []);
    this.mp.get(key).push([timestamp, value]);
};

TimeMap.prototype.get = function(key, timestamp) {
    const v = this.mp.get(key);
    if (!v) return "";
    let lo = 0, hi = v.length - 1, ans = -1;
    while (lo <= hi) {
        const m = (lo + hi) >> 1;
        if (v[m][0] <= timestamp) { ans = m; lo = m + 1; }
        else hi = m - 1;
    }
    return ans === -1 ? "" : v[ans][1];
};

class TimeMap {
    private Map<String, List<int[]>> times;
    private Map<String, List<String>> values;

    public TimeMap() {
        times = new HashMap<>();
        values = new HashMap<>();
    }

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

    public String get(String key, int timestamp) {
        List<int[]> ts = times.get(key);
        if (ts == null) return "";
        int lo = 0, hi = ts.size() - 1, ans = -1;
        while (lo <= hi) {
            int m = (lo + hi) >>> 1;
            if (ts.get(m)[0] <= timestamp) {
                ans = m;
                lo = m + 1;
            } else {
                hi = m - 1;
            }
        }
        return ans == -1 ? "" : values.get(key).get(ans);
    }
}

class TimeMap {
    mp: Map<string, [number, string][]>;
    constructor() {
        this.mp = new Map();
    }
    set(key: string, value: string, timestamp: number): void {
        if (!this.mp.has(key)) this.mp.set(key, []);
        (this.mp.get(key) as [number, string][]).push([timestamp, value]);
    }
    get(key: string, timestamp: number): string {
        const v: [number, string][] | undefined = this.mp.get(key);
        if (!v) return "";
        let lo: number = 0, hi: number = v.length - 1, ans: number = -1;
        while (lo <= hi) {
            const m: number = (lo + hi) >> 1;
            if (v[m][0] <= timestamp) { ans = m; lo = m + 1; }
            else hi = m - 1;
        }
        return ans === -1 ? "" : v[ans][1];
    }
}