981. Time Based Key-Value Store

Time Based Key-Value Store

Problem Description 

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.

Approach) Hashtable

Idea:

I simply combine the key and timestamp into a composite key and use that to store stuff in the hashmap. It's a pretty straightforward solution.

Note about the usage of a string literal: In JavaScript, ${key}${timestamp} means key + timestamp, it's just a simple way to combine two strings into one. e.g. if key = "foo" and timestamp = 2, combinedKey = foo2.

Code:

var TimeMap = function() {
    this.map = {};
};

/** 
 * @param {string} key 
 * @param {string} value 
 * @param {number} timestamp
 * @return {void}
 */
TimeMap.prototype.set = function(key, value, timestamp) {
    var combinedKey = `${key}${timestamp}`;
    this.map[combinedKey] = value;
};

/** 
 * @param {string} key 
 * @param {number} timestamp
 * @return {string}
 */
TimeMap.prototype.get = function(key, timestamp) {
    while (timestamp > 0) {
        var combinedKey = `${key}${timestamp}`;
        if (combinedKey in this.map) return this.map[combinedKey];
        timestamp -= 1;
    }

    return '';
};

/** 
 * Your TimeMap object will be instantiated and called as such:
 * var obj = new TimeMap()
 * obj.set(key,value,timestamp)
 * var param_2 = obj.get(key,timestamp)
 */

Approach) Hashtable + Binary Search

/**
 * Initialize your data structure here.
 */
var TimeMap = function() {
  this.map = new Map();
};

/**
 * @param {string} key
 * @param {string} value
 * @param {number} timestamp
 * @return {void}
 */
TimeMap.prototype.set = function(key, value, timestamp) {
  if (!this.map.has(key)) this.map.set(key, []);
  this.map.get(key).push({ timestamp, value });
};

/**
 * @param {string} key
 * @param {number} timestamp
 * @return {string}
 */
TimeMap.prototype.get = function(key, timestamp) {
    if (!this.map.has(key)) return "";
    return this.binarySearch(this.map.get(key), timestamp);
};

TimeMap.prototype.binarySearch = function(arr, targetTimestamp) {
    let l = 0;
    let r = arr.length - 1;
    
    while (l < r) {
        const mid = Math.floor((l + r) / 2);
        
        if (arr[mid].timestamp < targetTimestamp) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    
    if (arr[l] && arr[l].timestamp <= targetTimestamp) return arr[l].value;
    if (arr[l - 1] && arr[l - 1].timestamp <= targetTimestamp) return arr[l - 1].value;

    return "";
};



/**
 * Your TimeMap object will be instantiated and called as such:
 * var obj = new TimeMap()
 * obj.set(key,value,timestamp)
 * var param_2 = obj.get(key,timestamp)
 */

Conclusion:

That’s all folks! In this post, we solved LeetCode problem #981. Time Based Key-Value Store

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!