Time Based Key-Value Store medium

Problem Statement

Design a time-based key-value store class TimeMap. The class should support two operations:

1. set(string key, string value, int timestamp): Stores the key key with the value value at the given timestamp timestamp.
2. get(string key, int timestamp): Returns the value associated with key at the given timestamp timestamp. If there are multiple values with the same key and different timestamps, return the value associated with the largest timestamp less than or equal to the given timestamp. If there are no values associated with key, return "".

Example 1

Input: ["TimeMap","set","get","get","set","get","get"] [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]] Output: [null,"bar","bar","bar","bar2","bar2","bar2"]

Explanation:

• TimeMap(): Initializes a new TimeMap object.
• set("foo", "bar", 1): Stores the key "foo" with value "bar" at timestamp 1.
• get("foo", 1): Returns "bar", which is the value at timestamp 1.
• get("foo", 3): Returns "bar", because the latest timestamp less than or equal to 3 is 1.
• set("foo", "bar2", 4): Stores the key "foo" with value "bar2" at timestamp 4.
• get("foo", 4): Returns "bar2", which is the value at timestamp 4.
• get("foo", 5): Returns "bar2", because the latest timestamp less than or equal to 5 is 4.

Example 2

Input: ["TimeMap","set","set","get","get","get","get","get"] [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]] Output: [null,null,null,"", "high","high","low","low"]

Steps

1. Data Structure: Use a map to store the key-value pairs. The value associated with each key should be a vector of pairs, where each pair contains a timestamp and its corresponding value. This allows us to store multiple values for the same key at different timestamps.

2. set(string key, string value, int timestamp): Add a new pair (timestamp, value) to the vector associated with the given key in the map.

3. get(string key, int timestamp):

   • If the key doesn't exist in the map, return "".
   • Perform a binary search on the vector of pairs associated with the key to find the largest timestamp less than or equal to the given timestamp.
   • Return the value associated with that timestamp.

Explanation

The code uses a map to store the key-value pairs, where the key is the string key and the value is a vector of pair<int, string> representing the timestamp and value. This allows us to efficiently store and retrieve multiple values for the same key at different timestamps. The get function uses binary search to efficiently find the appropriate value for the given timestamp.

Code

#include <map>
#include <vector>
#include <algorithm>

using namespace std;

class TimeMap {
public:
    TimeMap() {}

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

    string get(string key, int timestamp) {
        auto it = data.find(key);
        if (it == data.end()) return "";

        auto& pairs = it->second;
        auto it2 = upper_bound(pairs.begin(), pairs.end(), make_pair(timestamp, ""));
        if(it2 == pairs.begin()) return ""; // No timestamp <= given timestamp
        return (--it2)->second;
    }

private:
    map<string, vector<pair<int, string>>> data;
};

Complexity

• Time Complexity:
  • set: O(log n) on average due to push_back (amortized constant time) and map insertion (logarithmic).
  • get: O(log n) due to binary search on the vector of pairs.
• Space Complexity: O(N) where N is the total number of (key, value, timestamp) entries. The space used is proportional to the number of entries stored.