Time Based Key Value Store

Problem Description

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 stamp 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 such values, it returns "".

Examples

Constraints

• 1 <= key.length, value.length <= 100
• key and value consist of lowercase English letters and digits.
• 1 <= timestamp <= 10⁷
• All the timestamps in set are strictly increasing.
• At most 2 * 10⁵ calls will be made to set and get.

Mapping Keys to Sorted Timestamp Arrays

Since the timestamps in set calls are strictly increasing, they are naturally sorted. We can map each key to a list of pairs (timestamp, value) in a hash map. When calling get(key, timestamp):

• Retrieve the list of pairs for the key from the map.
• If no list exists, return "".
• Run binary search on the list to find the largest timestamp that is less than or equal to the query timestamp. Return the corresponding value.

Solution 1: Hash Map with Binary Search on Timestamps

Store elements in list arrays inside a hash map, query values using binary search.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class TimeMap {
    private static class DataNode {
        int timestamp;
        String value;
        DataNode(int timestamp, String value) {
            this.timestamp = timestamp;
            this.value = value;
        }
    }

    private HashMap<String, List<DataNode>> map;

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

    public void set(String key, String value, int timestamp) {
        map.putIfAbsent(key, new ArrayList<>());
        map.get(key).add(new DataNode(timestamp, value));
    }

    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) return "";
        List<DataNode> list = map.get(key);

        // Binary search for the largest timestamp <= query timestamp
        int left = 0;
        int right = list.size() - 1;
        String res = "";

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid).timestamp <= timestamp) {
                res = list.get(mid).value; // record potential candidate
                left = mid + 1; // look for larger timestamps
            } else {
                right = mid - 1;
            }
        }
        return res;
    }
}

class TimeMap:
    def __init__(self):
        self.map = {}  # maps key to a list of (timestamp, value)

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

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

#include <unordered_map>
#include <vector>
#include <string>

class TimeMap {
private:
    struct DataNode {
        int timestamp;
        std::string value;
    };
    std::unordered_map<std::string, std::vector<DataNode>> map;

public:
    TimeMap() {}

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

    std::string get(std::string key, int timestamp) {
        if (map.find(key) == map.end()) return "";
        const auto& list = map[key];

        int left = 0;
        int right = list.size() - 1;
        std::string res = "";

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

Complexity Analysis

• Time Complexity: set takes O(1) time. get takes O(log n) time where n is the number of values stored for the query key.
• Space Complexity: O(N) auxiliary space to store all key-value entries in the hash map.

Where It Breaks

If the timestamp inputs are not sorted during set calls, this binary search method fails. Under those conditions, we would have to sort the lists before running queries (taking O(n log n)) or use self-balancing search trees (like TreeMap in Java).

Common Mistakes

• Incorrect check conditions: Using strict < instead of <= when comparing timestamps. The problem requires returning values where the timestamp is less than or equal to the query.
• Loop termination: Returning an empty string immediately if the first element is larger than target, which is correct, but failing to continue looking for larger matching candidates when a valid match is found.

Frequently Asked Questions

Why does this count as version control? By mapping timestamps to values, we can reconstruct the exact state of any key at any point in history.

What happens if multiple entries have the same timestamp? The constraints guarantee that timestamps in set are strictly increasing, preventing duplicate timestamps for a single key.

← All Problems