Time Based Key-Value Store medium

Problem Statement

Design a time-based key-value store class TimeMap. The class supports two methods:

1. set(string key, string value, int timestamp): Stores the key key with the value value at the given timestamp timestamp. If the key already exists at a specific timestamp, the previous value will be overwritten.

2. get(string key, int timestamp): Returns the value of the key key at the given timestamp timestamp. If the key does not exist at this timestamp, it should return the latest value that was set before this timestamp. If there is no such value, it should return "".

Constraints:

• 1 <= key.length <= 100
• 1 <= value.length <= 100
• key consists of lowercase English letters and digits.
• value consists of lowercase English letters and digits.
• 1 <= timestamp <= 10^7
• All the timestamps timestamp of set are strictly increasing.
• At most 2 * 10^5 calls will be made to set and get.

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" (the latest value set before timestamp = 3)
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" (the latest value set before timestamp = 5)

Example 2

Input:

["TimeMap", "set", "set", "get", "get", "get"]
[[], ["love", "high", 10], ["love", "low", 20], ["love", 5], ["love", 10], ["love", 15]]

Output:

[null, null, null, "", "high", "high"]

Explanation:

TimeMap timeMap = new TimeMap();
timeMap.set("love", "high", 10);  // store the key "love" and value "high" along with timestamp = 10
timeMap.set("love", "low", 20);  // store the key "love" and value "low" along with timestamp = 20
timeMap.get("love", 5);          // return "" (no value set before timestamp = 5)
timeMap.get("love", 10);         // return "high"
timeMap.get("love", 15);         // return "high" (the latest value set before timestamp = 15)

Steps

1. Data Structure: Use a dictionary to store key-value pairs. The value associated with each key will be a list of (timestamp, value) pairs, sorted by timestamp. This allows efficient retrieval of the latest value before a given timestamp.

2. set(string key, string value, int timestamp):

   • If the key exists in the dictionary, append the new (timestamp, value) pair to its list.
   • Otherwise, create a new list with the (timestamp, value) pair and add it to the dictionary.

3. get(string key, int timestamp):

   • If the key doesn't exist, return "".
   • Perform a binary search on the list of (timestamp, value) pairs associated with the key to find the latest timestamp less than or equal to the given timestamp.
   • Return the value associated with that timestamp.

Explanation

The solution uses a dictionary to store the data, mapping keys to a list of (timestamp, value) pairs. This allows for efficient storage and retrieval of data. The use of binary search in the get method ensures that the retrieval of the latest value before a given timestamp happens in logarithmic time. This is crucial for maintaining efficiency with a large number of calls.

Code

using System;
using System.Collections.Generic;
using System.Collections;

public class TimeMap
{
    private Dictionary<string, List<(int timestamp, string value)>> data;

    /** Initialize your data structure here. */
    public TimeMap()
    {
        data = new Dictionary<string, List<(int timestamp, string value)>>();
    }

    public void Set(string key, string value, int timestamp)
    {
        if (!data.ContainsKey(key))
        {
            data[key] = new List<(int, string)>();
        }
        data[key].Add((timestamp, value));
    }

    public string Get(string key, int timestamp)
    {
        if (!data.ContainsKey(key))
        {
            return "";
        }

        List<(int, string)> list = data[key];
        int left = 0, right = list.Count - 1;
        int resultIndex = -1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (list[mid].timestamp <= timestamp)
            {
                resultIndex = mid;
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }

        return resultIndex == -1 ? "" : list[resultIndex].value;
    }
}

Complexity

• Time Complexity:

  • set: O(1) on average (amortized), O(n) in the worst case (if a key's list needs to be resized). The addition to the list is constant time, assuming an amortized analysis of list resizing.
  • get: O(log n), where n is the number of (timestamp, value) pairs associated with a key 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 (timestamp, value) pairs for any single key. The space is proportional to the total number of entries stored.