Very very simple and understandable soultion using maps


#1

int counter=0,cap=0;
unordered_map<int,int> hash2,hash3;
map<int,int> hash1;
// hash1…{time,key}
//hash2…{key,time}
//hash3…{key,vaue}
//each key will have a unique time counter
LRUCache::LRUCache(int capacity)
{
hash2.clear();
hash1.clear();
hash3.clear();
counter=0;
cap=capacity;
}

int LRUCache::get(int key)
{
if(cap==0) return -1;
if(hash3.find(key)==hash3.end()) return -1;

counter+=1;
int previous_time_for_this_key=hash2[key];
//updating the new time
hash2[key]=counter;
//now change the time for this key in hash1
hash1.erase(previous_time_for_this_key);
hash1[counter]=key;

return hash3[key];

}

void LRUCache::set(int key, int value)
{
if(cap==0) return ;
if(hash3.find(key)!=hash3.end())
{
hash3[key]=value;
counter+=1;
int previous_time_for_this_key=hash2[key];
//updating the new time
hash2[key]=counter;
//now change the time for this key in hash1

    hash1.erase(previous_time_for_this_key);
    hash1[counter]=key;
    return;
}
else if(hash3.size()==cap)
{
    //when size hits capacity we have to clear the LRU
    int key=hash1[hash1.begin()->first];
    hash2.erase(key);
    hash3.erase(key);
    hash1.erase(hash1.begin());
    
}
// new key is being added and cache size is less than capacity
counter+=1;
hash3[key]=value;
hash2[key]=counter;
hash1[counter]=key;

}


#2

A nice solution.Well written