মান লেযিয়ে আমাদের একটি টাইম-বেসড কি-ভ্যালু স্টোর ক্লাস TimeMap বানাতে হবে, যা দুটি অপারেশন সাপোর্ট করে।
set(string key, string value, int timestamp): এটি কি, ভ্যালু এবং দिये गये টাইমস্ট্যাম্প স্ট্রোর করবে।
get(string key, int timestamp): এটি এমন একটি ভ্যালু রিটার্ন করবে যাতে set(key, value, timestamp_prev) আগে কল করা হয়েছে, যেখানে timestamp_prev <= timestamp।
যদি এমন একাধিক ভ্যালু থাকে, তখন সবচেয়ে বড় timestamp_prev वाला ভ্যালু রিটার্ন করতে হবে। যদি এমন কোনো ভ্যালু না থাকে, খালি স্ট্রিং ("") রিটার্ন করবে। নিচের মতো ফাংশন কল করলে - set("foo","bar",1), get("foo",1), get("foo",3), set("foo","bar2",4), get("foo",4), get("foo",5) - আউটপুট হবে: [null, "bar", "bar", null, "bar2", "bar2"]
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
একটি ম্যাপ m সংজ্ঞায়িত করুন
set() মেথড হবে - m[key]-এ (timestamp, value) ইনসার্ট করুন
get() মেথড নিচের মতো কাজ করবে -
ret := খালি স্ট্রিং
v := m[key]
low := 0, high := v.size() - 1
যখন low <= high
mid := low + (high - low) / 2
যদি v[mid].first <= timestamp হয়, ret := v[mid].second এবং low := mid + 1
অন্যথায় high := mid - 1
ret রিটার্ন করুন
নিচের বাস্তবায়নটি দেখে আরও ভালো বুঝতে পারবেন -
উদাহরণ
#include <bits/stdc++.h> using namespace std; class TimeMap { public: /** Initialize your data structure here. */ 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; } }; 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; }ইনপুট
Initialize it then call set and get methods as follows: set("foo","bar",1)) get("foo", 1)) get("foo", 3)) set("foo","bar2",4)) get("foo", 4)) get("foo", 5))আউটপুট
bar bar bar2 bar2
