DEQUE, MAP & TIMER (Simple Solution - No pointer manipulation)


  • 0
    C
    class LRUCache{
    public:
     // last key in deque, such that it wasn't inserted again at a later time, is the least recently used key
    
    unordered_map<int,int> values; // map from key to values
    deque<pair<int,double> > priority; // dequeue containing pair(key,timer) where timer is the time the key was inserted
    unordered_map<int,double> timemap; // map from key to latest time it was inserted
    int cap; // max capacity
    double timer; // value that gets incremented for every operation
    
    LRUCache(int capacity) {
        cap = capacity;
        timer = 0.0;
    }
    
    void insert(int key, int value){
        timer+=0.001; // increment timer
        timemap[key] = timer; // update latest time for key
        priority.push_front(make_pair(key,timer)); // insert the key in the dequeue with its latest time
        values[key] = value; // set the new key value
    }
    
    int get(int key) {
        if(values.find(key) != values.end()){
            timer+=0.001;
            timemap[key] = timer; // update latest time for key
            priority.push_front(make_pair(key,timer)); // insert the key in the dequeue with its latest time
            return values[key]; // return value of key
        }
        else
            return -1;
    }
    
    void set(int key, int value) {
        if(values.find(key) != values.end() || values.size()<cap) // case if key already exists or max capacity is not reached
            insert(key,value);
        else{ // case if key doesn't exist and max capacity is reached
                pair<int,double> last = priority.back();
                while(last.second != timemap[last.first]){ // find the least recently used key 
                    priority.pop_back();
                    last = priority.back();
                }
                values.erase(last.first); // remove the least recently used key from values as we no longer need it
                timemap.erase(last.first); // remove the least recently used key from time map as we no longer need it
                insert(key,value);
            }
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.