मान लीजिए हमें एक टाइम-बेस्ड की-वैल्यू स्टोर क्लास TimeMap बनानी है जो दो ऑपरेशन्स सपोर्ट करती है:
set(string key, string value, int timestamp): यह दिए गए टाइमस्टैम्प के साथ की और वैल्यू स्टोर करता है।
get(string key, int timestamp): यह एक वैल्यू लौटाता है जैसे कि set(key, value, timestamp_prev) पहले कॉल किया गया था, जहां timestamp_prev ≤ timestamp।
यदि ऐसी कई वैल्यूज़ हैं, तो वह वैल्यू लौटानी चाहिए जहां timestamp_prev सबसे बड़ा हो। यदि कोई ऐसी वैल्यू नहीं है, तो खाली स्ट्रिंग ("") लौटाएं।
समाधान दृष्टिकोण
एक मैप m परिभाषित करें जो की को (टाइमस्टैम्प, वैल्यू) जोड़ों के वेक्टर से मैप करता है
set() में: m[key] में (timestamp, value) जोड़ें
get() में: बाइनरी सर्च से सबसे बड़ा timestamp_prev ≤ timestamp खोजें
पाए जाने पर वैल्यू लौटाएं, अन्यथा खाली स्ट्रिंग
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class TimeMap {
public:
unordered_map<string, vector<pair<int, string>>> m;
TimeMap() { m.clear(); }
void set(string key, string value, int timestamp) {
m[key].push_back({timestamp, value});
}
string get(string key, int timestamp) {
string ret = "";
vector<pair<int, string>>& v = m[key];
int low = 0;
int high = v.size() - 1;
while(low <= high){
int mid = low + (high - low) / 2;
if(v[mid].first <= timestamp){
ret = v[mid].second;
low = mid + 1;
}else{
high = mid - 1;
}
}
return ret;
}
};
int main(){
TimeMap ob;
ob.set("foo","bar",1);
cout << (ob.get("foo", 1)) << endl;
cout << (ob.get("foo", 3)) << endl;
ob.set("foo","bar2",4);
cout << (ob.get("foo", 4)) << endl;
cout << (ob.get("foo", 5)) << endl;
return 0;
}
इनपुट
set("foo","bar",1) get("foo",1) get("foo",3) set("foo","bar2",4) get("foo",4) get("foo",5)
आउटपुट
bar bar bar2 bar2