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.

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

Note: All the timestamps timestamp of set are strictly increasing.

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"

Approach: Hash Map + Binary Search

The problem guarantees that all calls to set are made with strictly increasing timestamps. This is the crucial detail! It means that if we store the values for a specific key in an array as they come in, the array will naturally be sorted by timestamp.

Because the data is sorted, we can use Binary Search in the get method to efficiently find the largest timestamp that is less than or equal to the requested timestamp.

1. Initialization: Use a Hash Map (or plain JavaScript object/Map) where the key is the string key, and the value is an array of objects/tuples { val: value, time: timestamp }.
2. set(key, value, timestamp):
   • If the key doesn’t exist in our map, initialize it with an empty array.
   • Push the new { val: value, time: timestamp } object to the end of the array.
3. get(key, timestamp):
   • If the key doesn’t exist in our map, return "".
   • Otherwise, get the array for that key.
   • Initialize left = 0, right = array.length - 1, and res = "".
   • Perform a Binary Search:
     • mid = Math.floor((left + right) / 2)
     • If array[mid].time <= timestamp: This is a valid candidate. We record its value (res = array[mid].val) and try to find a closer (larger) valid timestamp by searching the right half (left = mid + 1).
     • If array[mid].time > timestamp: This timestamp is too far in the future. It’s invalid, so we must search the left half (right = mid - 1).
   • Return res.

Solution

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({ val: value, time: timestamp });
};

/** 
 * @param {string} key 
 * @param {number} timestamp
 * @return {string}
 */
TimeMap.prototype.get = function(key, timestamp) {
    if (!this.map.has(key)) return "";
    
    const values = this.map.get(key);
    let left = 0;
    let right = values.length - 1;
    let res = "";
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (values[mid].time <= timestamp) {
            res = values[mid].val;
            // Valid, but we want the largest possible valid timestamp, 
            // so we search the right half.
            left = mid + 1;
        } else {
            // Invalid, it's too large, search the left half.
            right = mid - 1;
        }
    }
    
    return res;
};

Complexity Analysis

• Time Complexity:
  • set(): $O(1)$ since pushing to the end of an array takes constant time.
  • get(): $O(\log n)$ where $n$ is the number of entries for the specific key. We perform a binary search over the array of timestamps.
• Space Complexity: $O(m)$ overall, where $m$ is the total number of set operations performed. We store every (value, timestamp) pair in our data structure.