Hello, reader 👋🏽 ! Welcome to day 6 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.
Today, I will be picking up LeetCode's daily challenge problem: Time Based Key-Value Store.
🤔 Problem Statement
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.
We have to implement the TimeMap class as follows:
TimeMap()Initialises the object of the data structure.void set(String key, String value, int timestamp): stores the key key with the value value at the given time timestamp.String get(String key, int timestamp): returns a value such that set was called previously, withtimestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".
Link to the question: Time Based Key-Value Store.
💬 Thought Process - Linear Search
- According to the problem, we need to design a data structure that stores items in
key => [timestamp => value]pairs. - Here a single key could have multiple mappings of
timestamp => value. - Intuition says that we map every value to the given time stamp, which can be done using a normal hash map, and also map every key to multiple
timestamp => valuepairs. - Hence, we could use something like a 2D hash map that allows two-level access. First to the string key that is mapped to
timestamp -> valueand second to integer timestamp that is mapped to string value. - Something like this:
- Now, this is the initial set up. But what about the set and get operations?
Set Operation
The set operation is straightforward. Given a
key,timestamp, andvalue, We check if the key exists:- Yes ? Then we get the
timestamp => valuelist associated to the givenkeyand add the newtimestamp => value. - No? Then we create add a new key to the store and then for that key, we associate a new pair of
timestamp => value.
- Yes ? Then we get the
Get Operation
The get operation is not straightforward as it looks like. There are some things to consider:
- What if the given
keyis not a part of the store?- Then we need to return
"".
- Then we need to return
- What if the given
keyis present, but the giventimestampis not present?- Then we need to return a value whose time (let's denote this by
timestamp') wheretimestamp' < timestampfor the given string key.- What if a
timestamp'is not present at all?- Then we need to return
"". This would be the case when the the given timestamp is smaller than all the timestamps for the given string key.
- Then we need to return
- What if a
- Then we need to return a value whose time (let's denote this by
- What if the given
keyandtimestampare both present?- Then we simply return the value associated with the given timestamp and key.
- What if the given
To find a
timestamp' < timestampwe will have to iterate through the list oftimestamp => valuepairs for the given key and select the appropriate value.
Now let's code this out!
👩🏽💻 Solution 1
- Below is the code for the above approach:
class TimeMap {
// store by key => [timestamp => value]
Map<String, Map<Integer, String>> store;
public TimeMap() {
store = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
// If the store already contains the key
if(store.containsKey(key)) {
store.get(key).put(timestamp, value);
}
// If not, add a mew key and [timestamp => value] pair for it
else {
Map<Integer, String> keyValue = new HashMap<>();
keyValue.put(timestamp, value);
store.put(key, keyValue);
}
}
public String get(String key, int timestamp) {
int maxTimeStamp = -1;
// if the key is present
if(store.containsKey(key)) {
// Then find a key such that it's the largest stamp
// smaller than given time stamp
for(int k: store.get(key).keySet()) {
if(timestamp == k) {
return store.get(key).get(timestamp);
}
maxTimeStamp = k < timestamp ? Math.max(maxTimeStamp, k) : maxTimeStamp;
}
}
// If no timestamp found
if(maxTimeStamp > timestamp || maxTimeStamp == -1) {
return "";
}
return store.get(key).get(maxTimeStamp);
}
}
/**
* 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);
*/
Time Complexity:
- Set Operation: O(1)
Constant look up for value, constant time for insertion
- Get Operation: O(n)
n => number of `timestamp => value` pairs. In the worst case, all the pairs are associated with the same key, and we will have to traverse the entire list to find the value mapped to timestamp.
Space Complexity: O(n)
n => number of `timestamp => value` pairs.
💬 Thought Process - Binary Search
- The issue with the previous approach is in the get operation which is
O(n). - Because we know that the timestamp for every value is strictly increasing, the pairs associated with every value will be sorted.
- We can use binary search to improve time complexity from
O(n)to O(log n)`. - But to use binary search, we need to convert the pair of
timestamp, valueto an array or list. - Since the size of the list of pairs is dynamic, we can use the dynamic list supported by languages (ArrayList in Java).
- We can store every
<timestamp, value>as a pair. (Here implemented using the Pair class in Java).
👩🏽💻 Solution 2
- Below is the code with binary search implemented in
getoperation:
class TimeMap {
HashMap<String, ArrayList<Pair<Integer, String>>> store;
public TimeMap() {
store = new HashMap();
}
// Every <timestamp, value> pair will be in sorted order
// as timestamp is strictly increasing
public void set(String key, String value, int timestamp) {
if(!store.containsKey(key)) {
store.put(key, new ArrayList());
}
store.get(key).add(new Pair(timestamp, value));
}
public String get(String key, int timestamp) {
// When there is no key, return ""
if(!store.containsKey(key)) {
return "";
}
ArrayList<Pair<Integer, String>> innerList = store.get(key);
int left = 0;
int right = innerList.size()-1;
// If the first key is lesser than the timestamp value, we return ""
if(timestamp < innerList.get(left).getKey()) {
return "";
}
// If the last value is less than or equal to the timestamp, we return ""
if(timestamp >= innerList.get(right).getKey()) {
return innerList.get(right).getValue();
}
// search for the timestamp within bounds [0, size-1]
while(left <= right) {
int mid = (left+right)/2;
if(innerList.get(mid).getKey() == timestamp) {
return innerList.get(mid).getValue();
}
if(innerList.get(mid).getKey() < timestamp) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return innerList.get(right).getValue();
}
}
/**
* 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);
*/
Time Complexity:
- Set Operation: O(1)
Constant look up for value, constant time for insertion
- Get Operation: O(log n)
n => number of `timestamp => value` pairs. In the worst case, all the pairs are associated with the same key, and we will have to perform binary search on the list to find the value mapped to timestamp.
Space Complexity: O(n)
n => number of `timestamp => value` pairs.
👩🏽💻 Alternative Solution 2 (Java)
- Instead of using a dynamic list, we can also use the following data structure
HashMap<String, TreeMap<Integer, String>>. - The
TreeMapclass stores key value pairs in the sorted order. - It also provides a method
floorKey(int key)that searches and returns avalue <= key. - Hence this method can be used instead of converting the inner map to a dynamic list and performing binary search on it.
- Below is the code using TreeMap:
class TimeMap {
Map<String, TreeMap<Integer, String>> store;
public TimeMap() {
store = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
if(!store.containsKey(key)) {
TreeMap<Integer, String> innerMap = new TreeMap<>();
store.put(key, innerMap);
}
store.get(key).put(timestamp, value);
}
public String get(String key, int timestamp) {
if(!store.containsKey(key)) {
return "";
}
int maxTimestamp = -1;
TreeMap<Integer, String> innerMap = store.get(key);
int firstKey = innerMap.firstKey();
int lastKey = innerMap.lastKey();
// If the given timestamp is less than the smallest key => then you return empty string
if(firstKey > timestamp) {
return "";
}
// If the time stamp is present, return the value mapped to it
if(innerMap.containsKey(timestamp)) {
return innerMap.get(timestamp);
}
// If the last key is smaller than time stamp, then you just return it.
if(lastKey < timestamp) {
return innerMap.get(lastKey);
}
// else return the greatest value smaller than timestamp
Integer timestamp_prev = innerMap.floorKey(timestamp);
return timestamp_prev == null ? "" : innerMap.get(timestamp_prev);
}
}
/**
* 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);
*/
Time Complexity:
- Set Operation: O(1)
Constant look up for value, constant time for insertion
- Get Operation: O(log n)
n => number of `timestamp => value` pairs. In the worst case, all the pairs are associated with the same key, and we will have to perform binary search on the list to find the value mapped to timestamp.
Space Complexity: O(n)
n => number of `timestamp => value` pairs.
Link to the GitHub repo for solution.
Conclusion
That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!
Thank you for reading!