Time Based Key-Value Store medium

Problem Statement

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps. Implement the TimeMap class:

• TimeMap(): Initializes the object.
• set(key: string, value: string, timestamp: number): Stores the key key with the value value at the given time timestamp.
• get(key: string, timestamp: string): Returns a value such that it was stored at a timestamp equal to or smaller than timestamp, among all values associated with key. Returns "" if there is no such value.

Example 1

Input: inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,"bar","bar","bar","bar2","bar2","bar2"]
Explanation: 
TimeMap kv;
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1
kv.get("foo", 1);  // output "bar"
kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie "bar"
kv.set("foo", "bar2", 4);
kv.get("foo", 4); // output "bar2"
kv.get("foo", 5); //output "bar2"

Example 2

Input: inputs = ["TimeMap","set","set","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15]]
Output: [null,"","high","high"]

Steps

1. Data Structure: We'll use a Map to store the key-value pairs. For each key, the value will be an array of [timestamp, value] pairs, sorted by timestamp. This allows for efficient binary search.

2. set(key, value, timestamp): Append the new [timestamp, value] pair to the array associated with the key. No sorting is needed at this point, since we'll handle sorting during get.

3. get(key, timestamp):

   • If the key doesn't exist, return "".
   • Perform a binary search on the sorted array of [timestamp, value] pairs to find the largest timestamp less than or equal to the given timestamp.
   • Return the corresponding value; if no such timestamp is found (binary search returns -1), return "".

Explanation

The key to efficiency here is using a Map for fast key lookups and a sorted array for each key to enable efficient binary search in get. A binary search has a time complexity of O(log n), where n is the number of entries for a given key. This is significantly better than a linear search.

Code

class TimeMap {
    private map: Map<string, [number, string][]>;

    constructor() {
        this.map = new Map();
    }

    set(key: string, value: string, timestamp: number): void {
        if (!this.map.has(key)) {
            this.map.set(key, []);
        }
        this.map.get(key)!.push([timestamp, value]);
    }

    get(key: string, timestamp: number): string {
        if (!this.map.has(key)) {
            return "";
        }

        const pairs = this.map.get(key)!;
        let low = 0;
        let high = pairs.length - 1;
        let result = "";

        while (low <= high) {
            const mid = Math.floor((low + high) / 2);
            if (pairs[mid][0] <= timestamp) {
                result = pairs[mid][1];
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }
}

Complexity

• Time Complexity:

  • set: O(1) on average (amortized O(1) due to potential array resizing)
  • get: O(log n), where n is the number of values associated with the given key. This is due to the binary search.

• Space Complexity: O(m * n), where m is the number of unique keys, and n is the maximum number of values associated with a single key. This is because we store all the timestamp-value pairs.