Well, the first and the main question here - where is polymorphism? The main() function doesn't use abstract class at all - it defines and solely uses LRUCache instance, while correct implementation would require a pointer to the base class to be used.
Second. We all have access to std::list<> which provides way better implementation of the linked list than custom made code in the Cache class.
So, I defined class LRUCache as standalone and used pair of standard STL containers to hold the cache and registry.
I had a little troubles with time errors, but i fixed it using mp.erase() function the less possible, moving the nodes "manually". Here's my working code. I hope you find it usefull.
class LRUCache: public Cache { public: LRUCache(int c) { cp = c; } void set(int k,int v) { Node *N; if(mp.empty()) //No nodes { N = new Node(k,v); tail = head = N; mp[k] = N; return; } auto it = mp.find(k); if(it != mp.end()) //In hash table { it->second->value = v; // update value if(head == it->second) //head? return; it->second->prev->next = it->second->next; if(tail == it->second) //tail? tail = tail->prev; else //in between? it->second->next->prev = it->second->prev; it->second->next = head; it->second->prev = NULL; head->prev = it->second; head = it->second; } else // No in hash table { N = new Node(head->prev,head,k,v); //new node head->prev = N; head = N; mp[k] = N; if(mp.size() > cp) //capacity? { tail = tail->prev; mp.erase(tail->next->key); delete tail->next; tail->next = NULL; } } } int get(int k) { auto it = mp.find(k); if(it != mp.end()) return it->second->value; return -1; } };
1<=key<=20, but M cache size could be from 1 to 1000! I could not derive need of cache size > key.
Attention! The test case on hackerrank is poorly designed.It may not cover all the situation that a LRU may occur.A personal suggestion is, due to that hackerrank is using the exact same API as leetcode, you can cut and paste all the code,except the main function, to leetcode to see what's going on. My AC answer:
class LRUCache:public Cache{ public: LRUCache(int i):Cache(){ cp = i; head = nullptr; tail = nullptr; } void set(int k,int v){ if(cp <= 0)return; if(mp.size() == 0){ Node *node = new Node(k,v); InsertIntoHead(node); mp.insert(make_pair(k,node)); } else if(mp.find(k)!=mp.end()){ auto it = mp[k]; it->value = v; InsertIntoHead(it); } else if(mp.size() < cp){ Node *node = new Node(k,v); InsertIntoHead(node); mp.insert(make_pair(k,node)); } else{ auto it = tail; mp.erase(it->key); LinkedListDelete(it); delete it; Node *node = new Node(k,v); InsertIntoHead(node); mp.insert(make_pair(k,node)); } } int get(int k){ if(mp.find(k) != mp.end()){ InsertIntoHead(mp[k]); return mp[k]->value; } else return -1; } private: void LinkedListDelete(Node* node){ if(!node)return; if(node-> prev) { node->prev->next = node->next; } if(node->next) { node->next->prev = node->prev; } if(node == head) { head = node->next; } if(node == tail) { tail = node->prev; } } void InsertIntoHead(Node* node) { if(!node)return; LinkedListDelete(node); if(head) head->prev = node; node->next = head; node->prev = nullptr; if(!tail) tail = node; head = node; } };
I got segmentation fault if I update the double linked-list by moving the hitted element into the front, but if I didn't update the double linked-list, the code pass all the test cases. I don't know why. Isn't the LRUCache supposed to update the cache when hits?
Sort 247 Discussions, By:
Please Login in order to post a comment