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
- 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 beMap<String, Map<Integer, String>>
- Algorithm: there is an interesting find when we look at the input constraints. The
timestamp
value passed into theset()
function will be strictly increased. That means if we keep track of the a list oftimestamp
, that list will have a strictly ascending order. This simply remind us ofBinary 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<>());
this.keyTimeMap.get(key).add(timestamp);
}
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 validtime
value. Else, we have alist
variable storing all timestamps value already get put into the database connecting with the keykey
. - if the value of
timestamp
is strictly smaller than the first value inlist
, 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 inlist
, 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 whichlist.get(i) <= timestamp
andlist.get(i + 1) > timestamp
. This will shows thatlist.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
andright = 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 ofmiddle
(anything smaller than index2
). 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 and6 > 5
so we ignore anything larger than6
. So:right = middle - 1 = 3
and continue the while - start 3rd while with
left = right = 3
:middle = 3
andlist.get(3) = 4
. This satisfies our check sincelist.get(3) = 4 <= 5
andlist.get(3 + 1) = 6 > 5
. So wereturn 4
. Finally, we just have to returnmap.get("foo").get(4)
as the final result
Top comments (0)