981. Time Based Key-Value Store

---

My Solution

The Key Idea for Solving This Coding Question

C++ Code

struct valueData {
    string value;
    int timestamp;
    valueData(string value, int timestamp) : value(value), timestamp(timestamp) {}
};

class TimeMap {
public:
    TimeMap() {

    }

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

    string get(string key, int timestamp) {
        auto iter = htbl.find(key);
        if (iter == htbl.end()) {
            return "";
        }

        vector<valueData> &valueList = iter->second;
        if (timestamp < valueList[0].timestamp) {
            return "";
        }
        if (valueList.back().timestamp < timestamp) {
            return valueList.back().value;
        }

        int left = 0, right = valueList.size() - 1;
        while (left < right) {
            int middle = left + (right - left + 1) / 2;
            if (timestamp < valueList[middle].timestamp) {
                right = middle - 1;
            } else {
                left = middle;
            }
        }
        if (timestamp < valueList[left].timestamp) {
            --left;
        }

        return valueList[left].value;
    }

private:
    unordered_map<string, vector<valueData>> htbl;
};

/**
 * 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);
 */

Time Complexity

• TimeMap
  $O(1)$
• set
  $O(1)$
• get
  $O(logn)$
  $n$ is the number of values associated with the queried key.

Space Complexity

• TimeMap
  $O(1)$
• set
  $O(m\cdot n)$
  $m$ is the number of key.
  $n$ is the number of values of their own key.
• get
  $O(1)$

Miscellane