# 981. Time Based Key-Value Store

Problem: Time Based Key Value Store

Understanding: This is a fascinating problem requiring us to design a new kind of map/database that could retrieve a `key: String` by `timestamp: int`.

The tricky part of the problem is that it requires us to retrieve data of a key such that the `return timestamp` is less than or equal to the `requested timestamp`.

For example, if we have a key: `foo` with the following timestamp: `2: "a", 4: "b", 6: "c"`. This means that timestamp `2` will be matched with value `a`, `4` be matched with value `b` and `6` be matched with value `c`.

So, if the request is `get(foo, 2)` we can simply return `a`. Similarly `get(foo, 3)` should also return `a` since `2` is already the closest timestamp to `3`.
And if the request is `get(foo, 5)`, that should return `b`. However, if the request is `get(foo, 1)`, we should return `""` since there is no timestamp available that is smaller than or equal to `1`.

Matching: We want to match this problem to a DataStructure or Algorithm that we already know

1. Data Structure: since we want a fast retrieval runtime, HashMap (or dictionary) is the best choice. And in order to retrieve value as `map.get(key).get(timestamp)`, the type of the map should be `Map<String, Map<Integer, String>>`
2. Algorithm: there is an interesting find when we look at the input constraints. The `timestamp` value passed into the `set()` function will be strictly increased. That means if we keep track of the a list of `timestamp`, that list will have a strictly ascending order. This simply remind us of `Binary Search` since we have a sorted array (list).

Implementation

We need to have a map of type `Map<String, Map<Integer, String>>` as discussed above.

But we also need another map of type `Map<String, List<Integer>>`. This map will store a list of `timestamps` connected with a specific `key` in ascending order. This will be used as source data for binary search.

``````class TimeMap {
Map<String, Map<Integer, String>> keyValueMap;
Map<String, List<Integer>> keyTimeMap;
public TimeMap() {
this.keyValueMap = new HashMap<>();
this.keyTimeMap = new HashMap<>();
}

public void set(String key, String value, int timestamp) {
this.keyValueMap.putIfAbsent(key, new HashMap<>());
this.keyValueMap.get(key).put(timestamp, value);

// create a list of time always in ascending order
this.keyTimeMap.putIfAbsent(key, new ArrayList<>());
}

private Integer findIndex(String key, int timestamp) {
// return -1 if we find nothing
// return i if time at i <= timestamp and time at i + 1 > time
// if timestamp < first element in the list => return -1
// if time stamp >= last element in the list, return the last index

// 1. check if the list exist
if (!this.keyTimeMap.containsKey(key)) {
return -1;
}

// 2. get the list and check the edge case
List<Integer> timeList = this.keyTimeMap.get(key);
int left = 0;
int right = timeList.size() - 1;

if (timestamp < timeList.get(left)) {
return -1;
} else if (timestamp >= timeList.get(right)) {
return timeList.get(right);
} else {
while (left <= right) {
int middle = (left + right) / 2;

if (middle <= timeList.size() - 1 && timeList.get(middle) <= timestamp && timeList.get(middle + 1) > timestamp) {
return timeList.get(middle);
} else if (timestamp > timeList.get(middle)) { // lef side is useless
left = middle + 1;
} else if (timestamp < timeList.get(middle)) { // right side is useless
right = middle - 1;
}
}
return -1;
}

}

public String get(String key, int timestamp) {
/**
Utilize binary search to find a place in the middle of the list in which index i <= time and index i + 1 > time. return i;
*/
// find the index of the current timestamp
int timeValue = this.findIndex(key, timestamp);

if (timeValue < 0) {
return "";
} else {
return this.keyValueMap.get(key).get(timeValue);
}
}
}

/**
* 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);
*/
``````

Explanation:

The constructor function `TimeMap()` should be easy to understand since we just initialize the maps needed for our implementation.

Similarly, `set()` method is just putting elements into the map like we discussed above.

The part that might be a little bit confusing is the `findIndex(String key, int timestamp)` function which is trying the find the `time` value that is closest to the requested `timestamp`.

• if there is no existing `key` stored in our database, return -1. This denoted that there is no valid `time` value. Else, we have a `list` variable storing all timestamps value already get put into the database connecting with the key `key`.
• if the value of `timestamp` is strictly smaller than the first value in `list`, we can also return -1 since there is no other suitable value.
• if the value of `timestamp` is larger than or equal to the last element in `list`, we return that last element since that is already the largest value we could possibly get.
• otherwise, we can start our binary search. The main go is to find an index `i` at which `list.get(i) <= timestamp` and `list.get(i + 1) > timestamp`. This will shows that `list.get(i)` is the maximum time value we can get.

For example, assume that we have a request `findIndex("foo", 5)` and we have an associated list of `timestamp` connecting with key `"foo"` is: [1, 2, 3, 4, 6, 7].

• start binary search with `left = 0` and `right = 5`.
• start 1st while: `middle = 2`. `list.get(2) = 3` This value does not satisfy anything and requires us to ignore anything on the left of `middle` (anything smaller than index `2`). So: `left = 3` and start new while loop
• start 2st while with `left = 3, right = 5`: `middle = (3 + 5) / 2 = 4`. `list.get(4) = 6` this also does not satisfy our checks and `6 > 5` so we ignore anything larger than `6`. So: `right = middle - 1 = 3` and continue the while
• start 3rd while with `left = right = 3`: `middle = 3` and `list.get(3) = 4`. This satisfies our check since `list.get(3) = 4 <= 5` and `list.get(3 + 1) = 6 > 5`. So we `return 4`. Finally, we just have to return `map.get("foo").get(4)` as the final result