can you plz help me what is the problem in my approach??
please help me with this sir , i have enrolled in so many courses at cb and this question is seriously taking a lot of time and effort and this doubt of mine is not cleared by anyone so plz help sir.
https://practice.geeksforgeeks.org/problems/lru-cache/1/?track=SPC-Queue&batchId=145
As you can see that i have make a map of key and its corresponding address in the deque i.e. unordered_map<int,deque<pair<int,int>>::iterator>map;
so whenever i see a key which already exists and i need to update its value then i just erase the corresponding key from deque by doing
dq.erase(map[key]) as map[key] contains the corresponding address value so dq.erase will delete that entry and then after pushing it to the back of the queue i am doing map[key]=–dq.end() which will put the new address in the of the inserted key in the map.
so what’s the fault in this approach??
and here is the code
class LRUCache
{
private:
int count;
deque<pair<int,int>>dq;
unordered_map<int,deque<pair<int,int>>::iterator>map;
int max_capacity;
public:
LRUCache(int capacity)
{
// constructor for cache
max_capacity=capacity;
count=0;
}
int get(int key)
{
// this function should return value corresponding to key
if(!map.count(key))
return -1;
else
{
int m=(*map[key]).second;
dq.erase(map[key]);
dq.push_back(make_pair(key,m));
map[key]=--dq.end();
return m;
}
}
void set(int key, int value)
{
// storing key, value pair
if(!map.count(key) && count!=max_capacity)
{
dq.push_back(make_pair(key,value));
map[key]=--dq.end();
count++;
}
else if(!map.count(key) && count==max_capacity)
{
int a=(dq.front()).first;
dq.pop_front();
map.erase(a);
dq.push_back(make_pair(key,value));
map[key]=--dq.end();
}
else if(map.count(key))
{
dq.erase(map[key]);
dq.push_back(make_pair(key,value));
map[key]=--dq.end();
}
}
};