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.
Below you can see my solution which passed in all test cases.
I have one remark, If I comment the function UpdateLastHit and submit, it will also pass all the tests.
It seems there is a corner cased not being tested. Does anyone have the same experience?
classLRUCache:Cache{private:// Member variable to distinguish between first // element added and remaining elementsboolm_first_node_added=false;// Iterator for mapstd::map<int,Node*>::iteratorit;// Add new NodevoidAddNode(intkey,intvalue);// Discard last item of list and add new NodevoidUpdateNewNode(intkey,intvalue);// Update Cache order after a get commandvoidUpdateLastHit(Node*node);public:// Public constructor with capacityLRUCache(intcapacity){cp=capacity;}// set new itemvoidset(intkey,intvalue);// get value from listintget(intkey);};intLRUCache::get(intkey){intret_value=0;try{it=mp.find(key);if(it!=mp.end()){Node*tmp=it->second;ret_value=tmp->value;// UpdateUpdateLastHit(tmp);/*std::cout << "Print" << std::endl; // Print from tail to head Node* x = tail; for (int i = 0; i < mp.size(); i++) { std::cout <<" i - " << i << " - " << x->key << " - " << x->value << std::endl; if (x->next != nullptr) { x = x->next; } else { break; } }*/// Print from head to tail/*x = head; for (int i = 0; i < mp.size(); i++) { std::cout <<" i - " << i << " - " << x->key << " - " << x->value << std::endl; if (x->prev != nullptr) { x = x->prev; } else { break; } }*/}else{ret_value=-1;}}catch(conststd::out_of_range&oor){std::cerr<<"Out of Range error: "<<oor.what()<<'\n';}returnret_value;}voidLRUCache::UpdateLastHit(Node*node){// If node requested is already head// no update neededif(node->value!=head->value&&node->key!=head->key){// If node is tail// linked list update shall be differentif(node==tail){Node*next_node=node->next;tail=next_node;next_node->prev=nullptr;}else{// Get previous and next nodeNode*prev_node=node->prev;Node*next_node=node->next;// Link previous and next nodeprev_node->next=next_node;next_node->prev=prev_node;}//Update headnode->prev=head;node->next=nullptr;head->next=node;head=node;}}voidLRUCache::set(intkey,intvalue){if(mp.size()<cp){//std::cout << "AddNode" << std::endl;AddNode(key,value);}else{//std::cout << "Update of list is needed" << std::endl;UpdateNewNode(key,value);}}voidLRUCache::AddNode(intkey,intvalue){// Create Node ptrNode*entry=newNode(key,value);if(!m_first_node_added){// Since it is first Node there is no prev or nextentry->prev=nullptr;}else{// If is not the first Node, set prev as the current headentry->prev=head;}// Next will always be null since the new node is added to the headentry->next=nullptr;// If it is not the first node, current Head will point to new node// Update the next entry for the previous headif(m_first_node_added){head->next=entry;}// Add/Update entry to mapmp[key]=entry;// Entry is always the new headhead=entry;// First Node added then is at same time tail and headif(!m_first_node_added){tail=entry;}// If first node is added// initialize variableif(!m_first_node_added){m_first_node_added=true;}}voidLRUCache::UpdateNewNode(intkey,intvalue){// Update tail first and remove current tailinttail_key=tail->key;tail=tail->next;tail->prev=nullptr;// remove old tailmp.erase(tail_key);// Add new entry as header// Create Node ptrNode*entry=newNode(key,value);// Copy next reference from current tailentry->prev=head;entry->next=nullptr;// Assign next entry to old headhead->next=entry;// Add entry to mapmp[key]=entry;// Set new headhead=entry;}
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 →
Hello,
Below you can see my solution which passed in all test cases.
I have one remark, If I comment the function UpdateLastHit and submit, it will also pass all the tests.
It seems there is a corner cased not being tested. Does anyone have the same experience?