Time Based Key-Value Store

Design a time-based key-value store. set(key, val, timestamp) stores with timestamp. get(key, timestamp) returns the value with the largest timestamp <= given timestamp.

Example 1

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

Solution Approach

HashMap>. Binary search on the list for each get.

Map> store.
set: append {timestamp, valIndex} to list.
get: binary search for largest timestamp <= query.

Java

import java.util.*;

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

    public void set(String key, String value, int timestamp) {
        store.computeIfAbsent(key, k->new ArrayList<>()).add(new long[]{timestamp, vals.size()});
        vals.add(value);
    }
    public String get(String key, int timestamp) {
        List<long[]> list = store.getOrDefault(key, Collections.emptyList());
        int lo=0, hi=list.size()-1, idx=-1;
        while (lo<=hi) {
            int mid=lo+(hi-lo)/2;
            if (list.get(mid)[0]<=timestamp) { idx=(int)list.get(mid)[1]; lo=mid+1; }
            else hi=mid-1;
        }
        return idx==-1 ? "" : vals.get(idx);
    }
}

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