We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<iostream>#include<vector>#include<map>#include<string>#include<algorithm>#include<set>#include<cassert>usingnamespacestd;structNode{Node*next;Node*prev;intvalue;intkey;Node(Node*p,Node*n,intk,intval):prev(p),next(n),key(k),value(val){};Node(intk,intval):prev(NULL),next(NULL),key(k),value(val){};};classCache{protected:map<int,Node*>mp;//map the key to the node in the linked listintcp;//capacityNode*tail;// double linked list tail pointerNode*head;// double linked list head pointervirtualvoidset(int,int)=0;//set functionvirtualintget(int)=0;//get function};classLRUCache:publicCache{private:intcount;public:LRUCache(intcp){this->cp=cp;count=0;}~LRUCache(){Node*temp=this->head;while(temp->next){if(temp->prev)deletetemp->prev;temp=temp->next;}deletetemp;mp.clear();}voidset(inta,intb){if(!mp[a]){if(count==0){Node*n=newNode(a,b);mp[a]=n;tail=head=n;}elseif(count<cp){Node*n=newNode(a,b);mp[a]=n;tail->next=n;Node*temp=tail;tail=tail->next;tail->prev=temp;}else{mp.erase(head->key);head->value=b;head->key=a;mp[head->key]=head;}count++;}else{Node*temp=mp[a];mp[tail->key]=temp;mp[a]=tail;temp->value=tail->value;temp->key=tail->key;tail->value=b;tail->key=a;}}intget(intkey){returnmp[key]?mp[key]->value:-1;}};intmain(){intn,capacity,i;cin>>n>>capacity;LRUCachel(capacity);for(i=0;i<n;i++){stringcommand;cin>>command;if(command=="get"){intkey;cin>>key;cout<<l.get(key)<<endl;}elseif(command=="set"){intkey,value;cin>>key>>value;l.set(key,value);}}return0;}return0;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Abstract Classes - Polymorphism
You are viewing a single comment's thread. Return to all comments →
Take my whiskey neat Solution