Massive Algorithms: LIKE CODING: MJ [1]

LIKE CODING: MJ [1]
http://www.mitbbs.com/article_t/JobHunting/33021795.html
put(key,value,time)
get(key, time)

要求get返回给定time前面的那个值.
implement a data structure to get a value of a key at a specific time

class Solution{

    unordered_map<int, vector<pair<int, int>>> hash;

public:

    void put(int key, int value, int time){

        hash[key].push_back(pair<int, int>(time, value));

}

    int get(int key, int time){

        vector<pair<int, int>> vec = hash[key];

        sort(vec.begin(), vec.end());//sort on first element of pair

        int l = 0, r = vec.size()-1;

        while(l<=r){

            int m = (l+r)/2;

            int t = vec[m].first;

            if(t==time) return vec[m].second;

            else if(t<time) l++;

            else r--;

}

}

};

Labels