Design Time-Based Key-Value Store

Problem

Design TimeMap with set(String key, String value, int timestamp) and get(String key, int timestamp). get returns the value with the LARGEST timestamp ≤ the query timestamp for that key, or "" if none.

Constraints

• 1 ≤ key.length, value.length ≤ 100
• 1 ≤ timestamp ≤ 10⁷
• timestamps for the same key are strictly increasing across set calls

Approach — Binary Search

This is a Binary Search problem. The idea: repeatedly halve the search space, discarding the half that can't contain the answer. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(log n) time.

Solution code

Python

import bisect
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, [])
        i = bisect.bisect_right(arr, (timestamp, chr(127)))
        return arr[i-1][1] if i else ""

Java

import java.util.*;

class TimeMap {
    private Map<String, TreeMap<Integer, String>> store = new HashMap<>();
    public void set(String key, String value, int timestamp) {
        store.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
    }
    public String get(String key, int timestamp) {
        TreeMap<Integer, String> tm = store.get(key);
        if (tm == null) return "";
        Map.Entry<Integer, String> e = tm.floorEntry(timestamp);
        return e == null ? "" : e.getValue();
    }
}

class Solution {}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.