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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. C++
  3. Classes
  4. Abstract Classes - Polymorphism
  5. Discussions

Abstract Classes - Polymorphism

Problem
Submissions
Leaderboard
Discussions

    You are viewing a single comment's thread. Return to all comments →

  • mlyymlyy
    6 years ago+ 3 comments

    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;
    	}
    };
    
    9|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature