Medium

Time Based Key-Value Store

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Examples

Input:["TimeMap", "set", "get", "get", "set", "get", "get"] [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]

Output:[null, null, "bar", "bar", null, "bar2", "bar2"]

TimeMap timeMap = new TimeMap(); timeMap.set("foo", "bar", 1); timeMap.get("foo", 1); // return "bar" timeMap.get("foo", 3); // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar". timeMap.set("foo", "bar2", 4); timeMap.get("foo", 4); // return "bar2" timeMap.get("foo", 5); // return "bar2"

Constraints

1 <= key.length, value.length <= 100
key and value consist of lowercase English letters and digits.
1 <= timestamp <= 10^7
All the timestamps timestamp of set are strictly increasing.
At most 2 * 10^5 calls will be made to set and get.

Hash Map + Binary Search

Approach

Since `set` is called with strictly increasing timestamps, we can store values in a hash map where the key is the string `key`, and the value is a list of `[value, timestamp]` pairs. This list will automatically be sorted by timestamp. For `get`, we can use binary search on this list to find the value with the largest timestamp that is `<= target_timestamp`.

Complexity Analysis

Time Complexity

O(1) for set, O(log N) for get

Space Complexity

O(N)

N is the number of set operations.

Solution.java

1class TimeMap {2    private Map<String, List<Pair<Integer, String>>> map;3
4    public TimeMap() {5        map = new HashMap<>();6    }7    8    public void set(String key, String value, int timestamp) {9        if (!map.containsKey(key)) {10            map.put(key, new ArrayList<>());11        }12        map.get(key).add(new Pair(timestamp, value));13    }14    15    public String get(String key, int timestamp) {16        if (!map.containsKey(key)) {17            return "";18        }19        20        List<Pair<Integer, String>> list = map.get(key);21        int left = 0;22        int right = list.size() - 1;23        String res = "";24        25        while (left <= right) {26            int mid = left + (right - left) / 2;27            if (list.get(mid).getKey() <= timestamp) {28                res = list.get(mid).getValue();29                left = mid + 1; // Search for a closer, larger timestamp30            } else {31                right = mid - 1;32            }33        }34        35        return res;36    }37}38// Note: Pair class assumed for Java (custom or javafx.util.Pair)39class Pair<K, V> {40    K key; V value;41    public Pair(K key, V value) { this.key = key; this.value = value; }42    public K getKey() { return key; }43    public V getValue() { return value; }44}