Time Based Key-Value Store

Design a time-based key-value store that stores multiple values for the same key at different timestamps and retrieves the value for a key at a given timestamp (or the latest before it).

Example 1

set("foo","bar",1), set("foo","bar2",4), get("foo",1)→"bar", get("foo",3)→"bar", get("foo",4)→"bar2"

Solution Approach

Store values in a list of (timestamp, value) pairs per key. Use binary search to find the latest timestamp <= given timestamp.

Store Map>.
On set: append (timestamp, value) to the list for key.
On get: binary search in the list for the largest timestamp <= query timestamp.
Return empty string if no valid timestamp found.

Java

import java.util.*;

class TimeMap {
    Map<String, List<int[]>> map = new HashMap<>();
    List<String> vals = new ArrayList<>();

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

    public String get(String key, int timestamp) {
        List<int[]> list = map.getOrDefault(key, Collections.emptyList());
        int lo = 0, hi = list.size() - 1, res = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (list.get(mid)[0] <= timestamp) { res = list.get(mid)[1]; lo = mid + 1; }
            else hi = mid - 1;
        }
        return res == -1 ? "" : vals.get(res);
    }
}

Time Complexity: set: O(1), get: O(log N)
Space Complexity: O(N) total