981.md

981. Time Based Key-Value Store

Solution 1 (time O(log(n)), space O(n))

class TimeMap {
public:
    unordered_map<string, vector<pair<int, string>>> M;
 
    /** Initialize your data structure here. */
    TimeMap() {
    }
    
    void set(string key, string value, int timestamp) {
        M[key].push_back(make_pair(timestamp, value));
    }
    
    string get(string key, int timestamp) {
        auto it = upper_bound(M[key].begin(), M[key].end(), make_pair(timestamp, "{"), [](const pair<int, string>& p1, const pair<int, string>& p2){
            return p1.first < p2.first;
        });
        if (it != M[key].begin()) {
            return prev(it)->second;
        } else {
            return "";
        }
    }
};

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap* obj = new TimeMap();
 * obj->set(key,value,timestamp);
 * string param_2 = obj->get(key,timestamp);
 */