Sponsored
Sponsored
This approach uses a HashMap where each key points to a sorted list of timestamp-value pairs. The 'set' function appends the value along with the timestamp to the list associated with the key. The 'get' function retrieves the value at a particular timestamp by performing a binary search to find the rightmost timestamp less than or equal to the requested timestamp.
Time Complexity: O(log n) for the 'get' operation and O(1) for the 'set' operation in terms of inserting, where n is the number of entries per key.
Space Complexity: O(n), where n is the number of entries in the TimeMap.
1class TimeMap {
2 constructor() {
3 this.store = new Map();
4 }
5 set(key, value, timestamp) {
6 if (!this.store.has(key)) {
7 this.store.set(key, []);
8 }
9 this.store.get(key).push({ timestamp, value });
10 }
11 get(key, timestamp) {
12 if (!this.store.has(key)) return "";
13 let values = this.store.get(key);
14 let left = 0, right = values.length - 1;
15 while (left <= right) {
16 const mid = Math.floor((left + right) / 2);
17 if (values[mid].timestamp <= timestamp) {
18 left = mid + 1;
19 } else {
20 right = mid - 1;
21 }
22 }
23 return right >= 0 ? values[right].value : "";
24 }
25}The JavaScript solution uses a Map data structure to store timestamps and values. The 'set' method appends each timestamp-value pair to an array. The 'get' function performs a binary search on this array to find the largest timestamp less than or equal to the given timestamp, ensuring a logarithmic time complexity for retrieval.
This approach is similar, but instead of using a helper library for the binary search, we implement it manually. This approach provides more control over the binary search process.
Time Complexity: O(log n) for the 'get' operation and O(1) for the 'set' operation, where n is the number of entries per key.
Space Complexity: O(n) total space used by the data structure, where n is total number of stored key-value pairs.
1#include <unordered_map>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
class TimeMap {
unordered_map<string, vector<pair<int, string>>> store;
public:
void set(string key, string value, int timestamp) {
store[key].emplace_back(timestamp, value);
}
string get(string key, int timestamp) {
if (store.find(key) == store.end()) return "";
auto& values = store[key];
int left = 0, right = values.size();
while (left < right) {
int mid = (left + right) / 2;
if (values[mid].first <= timestamp) left = mid + 1;
else right = mid;
}
return right > 0 ? values[right - 1].second : "";
}
};In C++, we use an unordered_map to keep track of all the keys. Every key maps to a vector of pairs, where each pair is a timestamp and its corresponding value. By manually coding the binary search, we find the accurate position to get the right timestamp in logarithmic time complexity.