Problem Description

The Time Based Key-Value Store problem asks you to design a data structure that can store multiple values for the same key, each associated with a unique timestamp. You must implement two operations:

• set(key, value, timestamp): Stores the value for the given key at the specified timestamp.
• get(key, timestamp): Returns the value associated with key at the largest timestamp less than or equal to timestamp. If there is no such timestamp, return an empty string "".

Key constraints:

• All set operations for a key are performed with strictly increasing timestamp values.
• The number of calls to set and get is reasonable (within typical Leetcode limits).
• There may be multiple values for a single key, each with a unique timestamp.

Thought Process

At first glance, you might consider storing all values for each key in a simple list and, for every get query, scanning through all timestamps to find the latest value that does not exceed the requested timestamp. However, this would be inefficient, especially if there are many values per key.

To optimize, we should take advantage of the strictly increasing order of timestamps. This means we can use efficient search techniques (like binary search) to quickly find the correct value for a get query. Thus, the problem shifts from simple storage to organizing data for fast retrieval.

Using a hash map (dictionary) to map each key to a list of (timestamp, value) pairs allows us to efficiently store and retrieve all versions of a key's value. For each get, we can perform a binary search on the timestamp list to find the appropriate value.

Solution Approach

We'll design a class with two main methods: set and get.

1. Data Structure:
   • Use a hash map (dictionary) where each key maps to a list of (timestamp, value) pairs.
   • Since timestamps are strictly increasing for each set operation, we can append new entries to the end of the list.
2. set(key, value, timestamp):
   • If the key does not exist, create a new list for it.
   • Append the (timestamp, value) pair to the list for that key.
3. get(key, timestamp):
   • If the key does not exist, return "".
   • Otherwise, perform a binary search on the list of timestamps to find the largest timestamp less than or equal to the given timestamp.
   • If found, return the corresponding value. If not, return "".
4. Binary Search Justification:
   • Since timestamps are always added in increasing order, the list is sorted, making binary search possible and efficient.

Example Walkthrough

Let's say we perform the following operations:

• set("foo", "bar", 1)
• set("foo", "bar2", 4)
• get("foo", 4) → returns "bar2"
• get("foo", 5) → returns "bar2"
• get("foo", 3) → returns "bar"
• get("foo", 0) → returns ""

Step-by-step:

• After first set: {"foo": [(1, "bar")]}
• After second set: {"foo": [(1, "bar"), (4, "bar2")]}
• get("foo", 4): Binary search finds timestamp 4 → returns "bar2".
• get("foo", 5): Binary search finds timestamp 4 (largest ≤ 5) → returns "bar2".
• get("foo", 3): Binary search finds timestamp 1 (largest ≤ 3) → returns "bar".
• get("foo", 0): No timestamp ≤ 0 → returns "".

Code Implementation

class TimeMap:
    def __init__(self):
        self.store = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = []
        self.store[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.store:
            return ""
        arr = self.store[key]
        # Binary search
        left, right = 0, len(arr) - 1
        res = ""
        while left <= right:
            mid = (left + right) // 2
            if arr[mid][0] <= timestamp:
                res = arr[mid][1]
                left = mid + 1
            else:
                right = mid - 1
        return res
      

class TimeMap {
public:
    unordered_map<string, vector<pair<int, string>>> store;

    TimeMap() {}

    void set(string key, string value, int timestamp) {
        store[key].push_back({timestamp, value});
    }

    string get(string key, int timestamp) {
        if (store.find(key) == store.end()) return "";
        const auto& arr = store[key];
        int left = 0, right = arr.size() - 1;
        string res = "";
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid].first <= timestamp) {
                res = arr[mid].second;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
};
      

class TimeMap {
    private Map<String, List<int[]>> timeMap;
    private Map<String, List<String>> valueMap;

    public TimeMap() {
        timeMap = new HashMap<>();
        valueMap = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        timeMap.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{timestamp});
        valueMap.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
    }

    public String get(String key, int timestamp) {
        if (!timeMap.containsKey(key)) return "";
        List<int[]> times = timeMap.get(key);
        List<String> values = valueMap.get(key);
        int left = 0, right = times.size() - 1;
        String res = "";
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (times.get(mid)[0] <= timestamp) {
                res = values.get(mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
}
      

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

TimeMap.prototype.set = function(key, value, timestamp) {
    if (!this.store[key]) this.store[key] = [];
    this.store[key].push([timestamp, value]);
};

TimeMap.prototype.get = function(key, timestamp) {
    if (!this.store[key]) return "";
    const arr = this.store[key];
    let left = 0, right = arr.length - 1;
    let res = "";
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid][0] <= timestamp) {
            res = arr[mid][1];
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return res;
};
      

Time and Space Complexity

Brute-force approach:

• For get, scan all timestamps for a key: O(N) time per query (where N is the number of values for that key).
• Space: O(N) for storing all values.

• set is O(1) per call (append to end of list).
• get is O(log N) per call (binary search over timestamps).
• Space: O(N) for all stored values and timestamps.

The binary search optimization makes get queries much faster, especially as the number of values per key grows.

Summary

The Time Based Key-Value Store problem is elegantly solved by combining a hash map for fast key lookup with sorted lists for each key's timestamped values. By leveraging the strictly increasing property of timestamps, we can use binary search to answer get queries efficiently. This structure allows us to handle a large number of operations quickly and is a good example of using classic data structures and algorithms (hash maps and binary search) to optimize for real-world constraints.