mediumBinary Search

Time Based Key-Value Store

Store timestamped string values. A get query returns the most recent value for its key at or before the requested time.

Work through the cases

3 examples

Input notation

One command per line: set key value timestamp or get key timestamp. Set times for each key strictly increase; tokens have no spaces.

Expected result

One value per get, or none when no suitable entry exists.

Case 1

Input

set a red 2
set a blue 5
get a 4
get a 5

Expected output

red
blue

Case 2

Input

get x 1
set x yes 3
get x 2

Expected output

none
none

Case 3

Input

set a x 1
get a 100

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

set timestamps are strictly increasing, so each key's history is already sorted. get wants the latest value at a time ≤ the query. A linear scan is too slow over 2 × 10^5 calls. Store (timestamp,value) lists per key and binary-search the upper bound.

We can use a hash table kvt to record key-value pairs, where the key is the string key and the value is an ordered set. Each element in the set is a tuple (timestamp, value), representing the value value corresponding to the key key at the timestamp timestamp.

When we need to query the value corresponding to the key key at the timestamp timestamp, we can use the ordered set to find the largest timestamp timestamp' such that timestamp' ≤ timestamp, and then return the corresponding value.

In terms of time complexity, for the set operation, since the insertion operation of the hash table has a time complexity of O(1), the time complexity is O(1). For the get operation, since the lookup operation of the hash table has a time complexity of O(1) and the lookup operation of the ordered set has a time complexity of O(log n), the time complexity is O(log n). The space complexity is O(n), where n is the number of set operations.

class TimeMap {
    private Map<String, TreeMap<Integer, String>> ktv = new HashMap<>();

    public TimeMap() {
    }

    public void set(String key, String value, int timestamp) {
        ktv.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
    }

    public String get(String key, int timestamp) {
        if (!ktv.containsKey(key)) {
            return "";
        }
        var tv = ktv.get(key);
        Integer t = tv.floorKey(timestamp);
        return t == null ? "" : tv.get(t);
    }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.