Time Based Key-Value Store ใน C++

คำอธิบายปัญหา

ออกแบบคลาส TimeMap ที่รองรับ 2 การดำเนินการ:

• set(key, value, timestamp): บันทึกค่าพร้อม timestamp
• get(key, timestamp): คืนค่าที่มี timestamp_prev <= timestamp และ timestamp_prev มากที่สุด หากไม่มีคืน ""

ตัวอย่าง: set("foo","bar",1), get("foo",1)="bar", get("foo",3)="bar", set("foo","bar2",4), get("foo",4)="bar2", get("foo",5)="bar2"

วิธีแก้ปัญหา

1. ใช้ unordered_map>> เก็บรายการ (timestamp, value) ต่อ key
2. set(): push_back ลง vector (timestamp เพิ่มขึ้นเรื่อยๆ ตามโจทย์)
3. get(): ใช้ Binary Search หา timestamp ที่มากที่สุดแต่ <= 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 = "";
        auto& v = m[key];
        int low = 0, 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; // bar
    cout << ob.get("foo", 3) << endl; // bar
    ob.set("foo", "bar2", 4);
    cout << ob.get("foo", 4) << endl; // bar2
    cout << ob.get("foo", 5) << endl; // bar2
    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