Time Based Key-Value Store

Leetcode 981. Time Based Key-Value Store

Problem

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.

Implement the TimeMap class:

• TimeMap() Initializes 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, with timestamp_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 "".

Example 1:

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"]

Explanation
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // store the key "foo" and value "bar" along with timestamp = 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); // store the key "foo" and value "bar2" along with timestamp = 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 <= 107
• All the timestamps timestamp of set are strictly increasing.
• At most 2 * 105 calls will be made to set and get.

Problem source: Leetcode 981. Time Based Key-Value Store

Solution

We have to have a data structure that stores keys and for each key, it has to have the ability to store multiple values. These values have two parts, timestamp and string.

Let’s assume we use a map to store the key and a vector (or list) to store the values. Each element of this vector is a pair data structure of int and string. Now, let’s put “cat” as a key and {1, “sleeping”} as our first value. This means that, at timestamp = 1 the key of “cat” has a value of “sleeping”.

Visually, this will look like below. In the bottom, we added a bar to see how timestamp is spread across time. You will find it useful in the next image.

Now, let’s put a new value for “cat” at timestamp = 4.

This will look like below.

Now, you see, at timestamp 4 we have a new value “meaw”. We also see at timestamp 2 and 3 “cat” will contain the value “sleeping” which was originally inserted at timestamp = 1!

Similarly, putting another value “eating” at timestamp = 9 will look like below.

We see at any timestamp between 4 and 8 inclusive, the value of “cat” was “meaw”.

Now, we will have to implement the get(key, timestamp) function. This function essentially asking, “Hey, can you tell me what was the value of this key was at time = timestamp?”. For example, what was the value of “cat” at timestamp = 7?

One interesting observation here is, since we are inserting values as time goes on, the vector will be created in a sorted by time fashion. This gives the clue that, we can use binary search to find the latest timestamp which is less than or equal to the asked timestamp by the get(key, timestamp) function.

For example, when we will be asked to find value when timestamp was 7, we should actually find the latest timestamp before 7 and get 4 and then return the value at 4 which is “meaw”. We need to modify a little of the binary search to get the lower bound of asked value.

Below code is commented with explanation of above analysis.

C++ Code

class TimeMap {
public:
    map<string, vector<pair<int, string>>> m;
    
    TimeMap() {
        // We are not doing anything with the constructor!
    }
    
    void set(string key, string value, int timestamp) {
        //For a single key, we are pushing the values in a vector
        //as {timestamp, value} pair. Since values are being pushed
        //as time passes, the vector for a key is automatically
        //being generated ascending by time
        m[key].push_back({timestamp, value});    
    }
    
    string get(string key, int timestamp) {
        
        int left = 0;
        int right = m[key].size(); //vector size of the asking key
        string ans = "";
        
        while(left < right){
            int mid = left + (right - left) / 2;
            /*
            Time value of the middle element is greater than timestamp.
            That means, timestamp is behind the middle element's time value,
            so, we should go to the left further ans that's why right mill come
            to mid.
            */
            if(m[key][mid].first > timestamp)
                right = mid;
            else{
                /*
                    mid is behind timestamp, this might be the last time our
                    value was updated. So, we will keep this value as answer
                    and explore more towards right. Since we will explore towards
                    right, left should move forward towards right and take the
                    place of mid + 1.
                */
                ans = m[key][mid].second;
                left = mid + 1;
            }
        }
        return ans;
    }
};

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

Conclusion

If you like this post or hate it, please write your opinion in the comment section. For more posts like this, please check below or go to the home page.

Happy Coding ! 🙂