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

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. Prepare
  2. C++
  3. Classes
  4. Abstract Classes - Polymorphism
  5. Discussions

Abstract Classes - Polymorphism

Problem
Submissions
Leaderboard
Discussions

Sort 305 Discussions, By:

recency

Please Login in order to post a comment

  • jyotirmoydasapd1
    1 month ago+ 0 comments

    include

    include

    class Cache { public: virtual void set(int key, int value) = 0; virtual int get(int key) = 0; };

    class LRUCache : public Cache { private: struct Node { int key; int value; Node* prev; Node* next; };

    std::unordered_map<int, Node*> mp;
    int cp;
    Node* head;
    Node* tail;
    

    public: LRUCache(int capacity) { cp = capacity; head = nullptr; tail = nullptr; }

    void set(int key, int value) {
        if (mp.find(key) != mp.end()) {
            // Update existing key and move it to the front.
            Node* node = mp[key];
            node->value = value;
            moveToFront(node);
        } else {
            // Create a new node and insert it at the front.
            Node* newNode = new Node{key, value, nullptr, nullptr};
            if (mp.size() == cp) {
                // Remove the least recently used item (tail).
                mp.erase(tail->key);
                removeTail();
            }
            mp[key] = newNode;
            addToFront(newNode);
        }
    }
    
    int get(int key) {
        if (mp.find(key) != mp.end()) {
            // Move the accessed item to the front and return its value.
            Node* node = mp[key];
            moveToFront(node);
            return node->value;
        }
        return -1; // Cache miss.
    }
    

    private: void moveToFront(Node* node) { if (node == head) { return; // Already at the front. } removeNode(node); addToFront(node); }

    void addToFront(Node* node) {
        node->next = head;
        node->prev = nullptr;
        if (head) {
            head->prev = node;
        }
        head = node;
        if (!tail) {
            tail = node;
        }
    }
    
    void removeNode(Node* node) {
        if (node->prev) {
            node->prev->next = node->next;
        } else {
            head = node->next;
        }
        if (node->next) {
            node->next->prev = node->prev;
        } else {
            tail = node->prev;
        }
    }
    
    void removeTail() {
        if (!tail) {
            return;
        }
        if (tail->prev) {
            tail->prev->next = nullptr;
        } else {
            head = nullptr;
        }
        delete tail;
        tail = nullptr;
    }
    

    };

    int main() { int n, capacity; std::cin >> n >> capacity;

    LRUCache lruCache(capacity);
    
    for (int i = 0; i < n; i++) {
        std::string command;
        std::cin >> command;
        if (command == "set") {
            int key, value;
            std::cin >> key >> value;
            lruCache.set(key, value);
        } else if (command == "get") {
            int key;
            std::cin >> key;
            std::cout << lruCache.get(key) << std::endl;
        }
    }
    
    return 0;
    

    }

    0|
    Permalink
  • hanbrianlee
    1 month ago+ 0 comments

    Here's a version without all the comments. Hope this helps.

    class LRUCache : public Cache{
        private:
            void update_usage(int k){            
                auto node = mp[k];            
                if(node == head || node == tail) return;                   
                node->prev->next = node->next;                        
                node->next->prev = node->prev;
                node->prev = nullptr; 
                node->next = head; 
                head->prev = node; 
                head = node;  
            }
        
        public:
            void set(int k, int v) override {            
                if(mp.find(k) != mp.end()){                
                    mp[k]->value = v;
                    update_usage(k);
                } 
                else{
                    Node* new_node = new Node(k, v);                
                    
                    if(head == nullptr){                    
                        head = new_node;
                        tail = new_node;
                        mp[k] = new_node;
                        return;
                    }
                    
                    if(mp.size() >= cp){                
                        mp.erase(tail->key);  
                        auto new_tail = tail->prev;                         
                        tail->prev->next = nullptr;
                        tail = new_tail;
                    }
                    
                    new_node->next = head;
                    head->prev = new_node;
                    head = new_node;
                    mp[k] = new_node;        
                }            
            }
            
            int get(int k) override {            
                if(mp.find(k) != mp.end()){                
                    update_usage(k);
                    return mp[k]->value;
                }
                else{
                    return -1;
                }
            }
            
            LRUCache(int capacity){
                cp = capacity;
            }     
    };
    
    0|
    Permalink
  • hanbrianlee
    1 month ago+ 0 comments

    Here's my solution.

    class LRUCache : public Cache{
        private:
            void update_usage(int k){
                // get the node pointed by the key
                // this function assumes k exists in mp
                auto node = mp[k];
                
                // if this node is the head, or tail, there's no need for management
                if(node == head || node == tail) return;       
                
                // otherwise, this node in the middle needs to be come the new head, and the rest pushed
                
                //node->prev should connect to node->next
                node->prev->next = node->next;            
                // and also node->next->prev should point to node->prev
                node->next->prev = node->prev;
                
                // node->next should be head. 
                node->prev = nullptr; // sever its prev connection
                node->next = head; // and it should point to the previous head
                head->prev = node; // also head's prev should point to node
                head = node;  // and it should be come the new head
            }
        
        public:
            void set(int k, int v) override {
                // cout << "set fn called" << endl;
                // the removing and adding to key will happen by map for O(1) operations
                // also at the same time use doubly linked list to take care of "recency", and same O(1)
                // operations to add and remove in parallel with the map operations            
                if(mp.find(k) != mp.end()){
                    // cache hit
                    // if cache is hit, then no need to add/remove any to the map, cp stays the same
                    // however recency deque should get updated
                    // and also of course the node's value
                    mp[k]->value = v;
                    update_usage(k);
                } 
                else{
                    // cache miss
                    // create a node based on k and v
                    Node* new_node = new Node(k, v);
                    
                    // if head and tail are empty, need to initialize them
                    if(head == nullptr){
                        // cout << "initialization" << endl;
                        head = new_node;
                        tail = new_node;
                        mp[k] = new_node;
                        return; // there's no dequeu list maintenance needed
                    }
                    
                    // if head was initialized, then need to check if capacity is reached
                    if(mp.size() >= cp){
                        // then the least used one, the tail, should be discarded
                        mp.erase(tail->key);  // from map               
                        auto new_tail = tail->prev;                         
                        tail->prev->next = nullptr;  // from deque            
                        // also need to assign a new tail  
                        tail = new_tail;
                    }
                    
                    // and should be added on the left side of the old head, and update the head
                    new_node->next = head;
                    head->prev = new_node;
                    head = new_node;
                    mp[k] = new_node;        
                }            
            }
            
            int get(int k) override {
                // cout << "hello in get" << endl;
                if(mp.find(k) != mp.end()){
                    // update the deque list accordingly
                    update_usage(k);
                    return mp[k]->value;
                }
                else{
                    return -1;
                }
            }
            
            LRUCache(int capacity){
                cp = capacity;
            }     
    };
    
    0|
    Permalink
  • chiragkhola47
    2 months ago+ 1 comment

    Am getting wrong answer for 10/12 test cases. ive manually matched my output for over 150 inputs from one of the cases so far and i cant find any value wrong. can someone please tell me what am doing wrong?

    class LRUCache:protected Cache { public: long int sizecap; LRUCache (int c){ sizecap=c; } void set(int k,int v) { if (mp.empty()) { Node* element = new Node(k,v); head=element; tail=element; mp[0]=element; // cout<<"1st value set"< bool exists=false; int ifexistkey; int size=mp.size(); for (long int i=0; ikey==k) { exists=true; ifexistkey=i; break; } } if (exists==true) {

                if (ifexistkey==mp.size()-1) {
                    tail=mp[ifexistkey]->prev;
                    // cout<<"prev set as tail"<<endl;
                    mp[ifexistkey]->next=head;
                    //  cout<<"head set as next"<<endl;
                    head->prev=mp[ifexistkey];
                    //  cout<<"head's prev set"<<endl;
                    head=mp[ifexistkey];
                }
                else if (ifexistkey==0) {
                    mp[ifexistkey]->value=v;
                    }
                else{
                mp[ifexistkey]->prev->next=mp[ifexistkey]->next;
                mp[ifexistkey]->next->prev=mp[ifexistkey]->prev;
                mp[ifexistkey]->next=head;
                head->prev=mp[ifexistkey];
                head=mp[ifexistkey];
                }
                    for (int i=1; i<=ifexistkey; i++) {
                        mp[i]=mp[i]->prev;
                    }
                    mp[0]=head;
                    // head->next=head+1;
                    // mp[ifexistkey+1]->prev=mp[ifexistkey];
                    // mp[ifexistkey]->next=mp[ifexistkey+1];
                }
            else if(exists==false){
                Node* element = new Node(k,v);
                int size=mp.size();
                if (size==sizecap) {
                    // cout<<"size cap case"<<endl;
                    tail=tail->prev;
                    // cout<<"tail set"<<endl;
                    mp.erase(sizecap-1);
                    // cout<<"erased"<<endl;
                    element->next=head;
                    head->prev=element;
                    head=element;
                    mp[0]=element;
                    int size=mp.size();
                    for (int i=1; i<size; i++) {
                        mp[i]=mp[i-1]->next;
                    }
    
                }
                else{
                        element->next=head;
                        // cout<<"og head set as next"<<endl;
                        head->prev=element;
                        // cout<<"element set as prev of og head"<<endl;
                        head=element;
                        // cout<<"element is made new head"<<endl;
                        mp[0]=element;
                        // cout<<"element is set as 0 key on map"<<endl;
                        int size=mp.size();
                        for (int i=1; i<=size; i++) {
                            mp[i]=mp[i-1]->next;
                        }
    
                        // cout<<"value at"<<k<<"set"<<endl;
                    }
                }       
        }
    }    
        int get(int keyval){
            bool exists=false;
            int ifexistkey;
            int size=mp.size();
            for (int i=0; i<size; i++) {
                if (mp[i]->key==keyval) {
                    exists=true;
                    ifexistkey=i;
                    break;
                }
            }
            if (exists==true) {
                    return mp[ifexistkey]->value;
                }
            else{
                return -1;
                } 
        }
    

    };

    0|
    Permalink
  • yymonsalve
    2 months ago+ 0 comments

    Mine has required destructors to free allocated memory, also it implements and underlying class LRUCacheList to deal with everything related with list's stuff.

    Compile with -DDEBUG option, to see what is done in background (user SMALL input files to this case).

    #include <iostream>
    #include <vector>
    #include <map>
    #include <string>
    #include <algorithm>
    #include <set>
    #include <cassert>
    using namespace std;
    
    struct Node{
       Node* next;
       Node* prev;
       int value;
       int key;
       Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){};
       Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){};
    };
    
    class Cache{
       
    protected: 
       map<int,Node*> mp; //map the key to the node in the linked list
       int cp;  //capacity
       Node* tail; // double linked list tail pointer
       Node* head; // double linked list head pointer
       virtual void set(int, int) = 0; //set function
       virtual int get(int) = 0; //get function
    
    };
    
    ostream &operator<<(ostream &o, const Node *n) {
        return o << '<' << n->key << ", " << n->value << '>';
            //<< ", me: " << (void *)n;
            //<< ", prev: " << n->prev << ", next: " << n->next;
    }
    
    // This is the double-linked list internally used by the LRUCache
    class LRUCacheList {
        Node *head;
        Node *tail;
        int   size;
    public:
        LRUCacheList() : head(NULL), tail(NULL), size(0) {}
        Node *getHead() const { return head; }
        Node *getTail() const { return tail; }
        int   getSize() const { return size; }
        bool  empty()   const { return head != NULL; }
    
        ~LRUCacheList() {
            //cout << "called destructor ~LRUCacheList()\n";
            Node *n = head, *np;
            while (n) {
                np = n->next;
                //cout << "freeing " << (void *)n << endl;
                delete n;
                n = np;
            }
            head = tail = NULL;
            size = 0;
        }
    
        /** Removes the last (tail) element of the cache-list */
        void removeTail() {
            if (tail != NULL) {
                if (tail->prev != NULL) tail->prev->next = NULL;
                Node *new_tail = tail->prev;
    
                if (head == tail) { head = NULL; }
                delete tail;
                tail = new_tail;
            }
            if (size > 0) --size;
        }
        /** Inserts a new element at the head of the cache-list */
        Node* insertFront(int key, int value) {
            /** Create a node (that will be the new head) with;
             *  - prev: NULL
             *  - next: former head
             */
            Node *new_head = new Node(NULL, head, key, value);
            // attach it as the head the list
            if (head != NULL) {
                head->prev = new_head;
                head = new_head;
            } else {    // empty list
                head = new_head;
                tail = new_head;
            }
            ++size;
            return head;
        }
        /** Moves a given node to the first position of the list. 
        */
        void promoteFront(Node *n) {
            if (head == n) return;
            
            if (n == tail) {
                tail = tail->prev;
                tail->next = NULL;
            } else {
                n->prev->next = n->next;
                n->next->prev = n->prev;
            }
    
            // attach it as the head the list
            if (head != NULL) {
                head->prev = n;
            } else {    // empty list
                tail = n;
            }
            n->prev = NULL;
            n->next = head;
            head = n;
        }
        /** Prints out the content of the list */
        friend ostream &operator<<(ostream &o, const LRUCacheList &l) {
            Node *n = l.getHead();
            while (n) {
                if (n != l.getHead()) { o << ", "; }
                o << n;
                n = n->next;
            }
            o << ", size(" << l.size << ")";
            return o;
        }
    };
    
    class LRUCache: public Cache {
    protected:
        int size_;
        LRUCacheList l_;
    public:
        LRUCache(int capacity) : size_(0) { Cache::cp = capacity; }
        
        /**
         * set() - Set/insert the value of the key, if present, otherwise add the key 
         * as the most recently used key. If the cache has reached its capacity, 
         * it should replace the least recently used key with a new key.
         */
        virtual void set(int key, int val) { 
            // look at the key in the map
            pair<map<int,Node*>::iterator, bool> ret = mp.insert({key, NULL});
            //auto [it, found] = mp.insert({key, NULL});    // c++17
            map<int,Node*>::iterator it = ret.first;
            //cout << (ret.second ? "true: " : "false: ") << "it->first: " << it->first << endl;
            //<< ", " << (it->second ? it->second : "NULL") << endl;
            //exit(0);
            if (ret.second == true) {
                // inserts the new element
                if (l_.getSize() == cp) { 
                    mp.erase(l_.getTail()->key);
                    l_.removeTail();
                }
                it->second = l_.insertFront(key, val);
            } else {
                // element already existed: 
                //   (1) update value
                //   (2) promote it at the front of the list
                it->second->value = val;    
                l_.promoteFront(it->second);
            }
            // update members that refer to the underlying linked-list
            size_ = l_.getSize();
            head  = l_.getHead();
            tail  = l_.getTail();
    #ifdef DEBUG
            cout << "set " << key << ' ' << val << endl;
            cout << "list is:\n  " << l_ << endl;
            cout << "map is:\n";
            for (auto &it: mp) {
                cout << "    " << it.first << ", " << it.second << endl;
            }
    #endif
        }
    
        /**
         * get() - Get the value (will always be positive) of the key if the key exists 
         * in the cache, otherwise return -1.
         */
        virtual int  get(int key) { 
            map<int,Node*>::iterator it = mp.find(key);
            if (it != mp.end()) {
                // THIS SHOULDN'T BE THIS WAY
                // This method IS NOT intended to change the structure
                // BUT, as per the specifications, it must promote the element
                // as the first of the list, if found
                l_.promoteFront(it->second);
                it->second = l_.getHead();
    
    #ifdef DEBUG
                cout << "get " << key << endl;
                cout << "list is:\n  " << l_ << endl;
                cout << "map is:\n";
                for (auto &it: mp) {
                    cout << "    " << it.first << ", " << it.second << endl;
                }
    #endif            
                return it->second->value;
            } else {
                return -1;
            }
        }
    };
    
    void testList() {
        LRUCacheList l;
        l.insertFront(1, 10);
        cout << "l:\n    " << l << endl;
        l.insertFront(2, 11);
        cout << "l:\n    " << l << endl;
        l.insertFront(3, 12);
        cout << "l:\n    " << l << endl;
        cout << "now, remove tail\n";
        l.removeTail();
        cout << "l:\n    " << l << endl;
        l.removeTail();
        cout << "l:\n    " << l << endl;
        l.removeTail();
        cout << "l:\n    " << l << endl;
        l.removeTail();
        cout << "l:\n    " << l << endl;
    
        l.insertFront(1, 10);
        cout << "l:\n    " << l << endl;
        l.insertFront(2, 11);
        cout << "l:\n    " << l << endl;
        l.insertFront(3, 12);
        cout << "l:\n    " << l << endl;
    
        cout << "Promote first\n";
        l.promoteFront(l.getHead());
        cout << "l:\n    " << l << endl;
        l.promoteFront(l.getHead()->next);
        cout << "l:\n    " << l << endl;
        l.promoteFront(l.getHead()->next->next);
        cout << "l:\n    " << l << endl;
    }
    
    int main() {
        int n, capacity,i;
    
        //testList();
        //exit(0); 
    
        cin >> n >> capacity;
        LRUCache l(capacity);
        for(i=0;i<n;i++) {
            string command;
            cin >> command;
            if(command == "get") {
                int key;
                cin >> key;
                cout << l.get(key) << endl;
            } 
            else if(command == "set") {
                int key, value;
                cin >> key >> value;
                l.set(key,value);
            }
        }
        return 0;
    }
    
    0|
    Permalink
Load more conversations

Need Help?


View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy