Time Based Key-Value Store | Leetcode | Binary Search

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:

1. TimeMap() :
2. Initialises the object of the data structure.
3. void set(String key, String value, int timestamp) :
4. Stores the key key with the value value at the given time timestamp.
5. String get(String key, int timestamp) 
6. Returns a value such that set was called previously, with timestamp_prev <= timestamp.
7. If there are multiple such values, it returns the value associated with the largest timestamp_prev.
8. If there are no values, it returns "".

Before we solve this question:

First let's understand why & how this technique is relevant to real world problems.

This question models real world scenarios where time based data is critical. Here are key areas where it applies:

1. Versioned Data Storage:
2. Document editing platform like Google docs, Microsoft word, each edit creates a version of the document at a specific time. If we want to retrieve the state of the document at a specific timestamps, we need a time based key value system.
3. Cache with Expiry:
4. In systems like CDNs, cached data is stored with timestamps. We might want to retrieve the latest cached value that hasn't expired yet.
5. Event Tracking & Logs:
6. Systems like datadog allow users to retrieve the state of a system i.e server status, metrics, logs at a specific timestamp.

Why It's a Good Problem for Interviews

1. Test data structure knowledge: It's demonstrates how adept one is using and fusing different data structures to solve a problem.
2. Teaches Trade-offs:
3. The problem encourages thinking about space i.e storing timestamps & values vs time i.e retrieving the right value efficiently.
4. Scalable Design:
5. The problem implicitly teaches how to design scalable systems where data grows over time. A stepping stone to design larger, more complex systems.

Step 1: Why Not Combine key and timestamp?

• If you use alice-1 as a key:
• Pro:
• It allows direct access to the value if the exact timestamp is requested.
• Con:
• You lose the ability to efficiently retrieve values for timestamps less than or equal to a given timestamp (get("alice", 2) wouldn't work since "alice-2" doesn't exist in your data).

Step 2: Storing Data as Nested Objects

{
 alice: {
  timeStamp1: value,
  timeStamp2: value,
 },
 foo: {
  1: "bar",
  4: "bar2",
 }
}

Benefits:

1. Organised Data:
2. Keys map to timestamps, and timestamps map to values.
3. Easy to see all timestamps associated with a key.
4. Direct Access:
5. If we know the exact timestamp, we can directly retrieve the value.

Challenges:

1. Objects don't have a natural order. To find the largest timestamp less than or equal to a given one, we'd need to :
2. Convert the keys into arrays
3. sort them
4. perform a search on them

Our Benefits align but to cop up with the challenges how about we change the data structure to

{
 alice: [
  { timestamp: 1, value: "happy" },
  { timestamp: 3, value: "sad" }
 ],
 foo: [
  { timestamp: 1, value: "bar" },
  { timestamp: 4, value: "bar2" }
 ]
}

Here:

1. Time stamps are ordered, since the set guarentee timestamps are strictly increasing, the array for each key is already sorted by timestamp.
2. Since the array is sorted we can use binary search for the lookup of time stamps.

we can simply use an object or map to store the data.

TimeMap.prototype.set = function (key, value, timestamp) {
    // if we already have an array just push into that
    // else create one
    if (this.myMap[key]) {
        this.myMap[key].push({
            timeStamp: timestamp,
            value
        })
    } else {
        this.myMap[key] = [{
            timeStamp: timestamp, value
        }]
    }
};

How about accessing the data?

instead of searching binary we can use built in functions like filter and what not. But if we want to use optimal searching strategy we wanna use binary search since the arrays are already sorted.

/** 
 * @param {string} key 
 * @param {number} timestamp
 * @return {string}
 */
TimeMap.prototype.get = function (key, timestamp) {    
    if (this.myMap[key]) {
        const data = this.myMap[key]
        //       using binary search
        let l = 0, r = data.length - 1, result = ""

        while (l <= r) {
            const mid = Math.floor((l + r) / 2)

            if (data[mid].timeStamp <= timestamp) {
                // we are at left sorted array
                // go to right
                result = data[mid].value
                l = mid + 1
            } else {
                // we are at right sorted array
                // go to left
                r = mid - 1
            }
        }
        return result
    } else {
        return ""
    }
};