Time Based Key-Value Store

Thought Process

The Time-Based Key-Value Store problem requires efficiently storing and retrieving values based on timestamps. Here's the approach:

Using Nested Maps - Use a map to store keys, where each key maps to another map of timestamps and values. For the 'set' operation, directly insert the value into the nested map using the key and timestamp. For the 'get' operation, use upper_bound to find the first timestamp greater than the given timestamp. If such a timestamp exists, move the iterator back to get the closest timestamp less than or equal to the given timestamp. If no valid timestamp is found, return an empty string.

class TimeMap {
public:
    map<string,map<int,string>> mp;
    TimeMap() {
        
    }
    void set(string key, string value, int timestamp) {
        
        mp[key][timestamp] = value; // Directly updating the map
    }
    
    string get(string key, int timestamp) {
        
        if(mp.count(key)){

            map<int,string> &treeMap =  mp[key];
            auto itr =  treeMap.upper_bound(timestamp); // Finding upper bound
            if(itr == treeMap.begin())
                return "";
            else{
                itr--; // Point to the iterator pointing to the timestamp i.e. less than equals to timestamp
                return itr->second;
            }
        }
        return "";
    }
};

Code Complexity

Time Complexity: O(log n)

The set operation takes O(log n) due to map insertion, and the get operation takes O(log n) due to the upper_bound operation.

Space Complexity: O(n)

The space complexity is O(n) due to the storage of all key-value pairs and their timestamps.

C++: Time-Based Key-Value Store

Thought Process

Code Complexity

Time Complexity: O(log n)

Space Complexity: O(n)