Abstract Classes - Polymorphism

Sort by

recency

|

330 Discussions

|

  • + 0 comments

    Abstract classes help decouple logic and enhance code reuse, especially when working with complex hierarchies or frameworks. A fundamental and elegant design principle in OOP . Betbricks7 Login ID and Password

  • + 0 comments

    Simple implementation avoiding pointer swapping hell. Getting LRU logic right is key here.

    class LRUCache : public Cache {
        
        void removeBack(){
            Node* currTail = tail;
            Node* newTail = tail->prev;
            int key = currTail->key;
            mp.erase(key);
            if(newTail)
                newTail->next = NULL;
            else 
                head = NULL;
            
            delete currTail;
        }
        
        void addNodeFront(int key, int val) {
            if(head){
                Node* newNode = new Node(NULL, head, key, val);
                if(mp.size() == cp)removeBack();
                head->prev = newNode;
                head = newNode;
                mp[key] = newNode; // Update mapping
            }
            else {
                Node* newNode = new Node(key, val);
                tail = head = newNode;
                mp[key] = newNode;
            }
        }
        
        void moveToHead(Node* arg, int newVal){
            Node *next, *prev;
            arg->value = newVal; // Update value
            if(arg == head)return; // If already head do nothing
            
            next = arg->next;
            prev = arg->prev;
            if(prev) // If previous is not NULL
                prev->next = next;
            if(next) // Same for next
                next->prev = prev;
            
            head->prev = arg;
            if(arg == tail)
                tail = arg->prev;
            arg->next = head;
            arg->prev = NULL;
            head = arg;
        }
        
        public:
            LRUCache(const int &cap){cp = cap;}
            void set(int key,int value) {
                if(mp.find(key) != mp.end()){
                    if(mp.size() > 1)
                        moveToHead(mp[key], value);
                    else 
                        head->value = value;
                }
                else
                    addNodeFront(key, value);
            }
            int get(int key) {
                if(mp.find(key) != mp.end()) {
                    moveToHead(mp[key], mp[key]->value); // W or w/o passess all tests
                    return mp[key]->value;
                }
                else
                    return -1;
            }
    };
    
  • + 0 comments

    why is doble linked list required here, can some please explain ?

  • + 0 comments

    class LRUCache: public Cache{ public: LRUCache(int c){cp = c; tail = nullptr; head = nullptr;} virtual void set(int key, int value) override{ map::iterator it = mp.find(key); Node* node = nullptr; if(it == mp.end()){ node =new Node(nullptr, head, key, value); if(mp.size() >= cp){ tail = tail->prev; tail->next->prev = nullptr; mp.erase(tail->next->key); delete tail->next; tail->next = nullptr; }else{ } if(tail == nullptr) tail = node; if(head) head->prev = node; head = node; mp[key] = node; }else{ it->second->value = value; node = it->second; if(node != head){ if(head->next == tail){ /* replace the order for head and tail*/ head = head->next; tail = tail->prev; tail->next = nullptr; head->prev = nullptr; head->next = tail; tail->prev = head; }else{ if(node == tail){ /* put the tail as a head*/ tail = tail->prev; tail->next = nullptr; node->prev = nullptr; node->next = head; head->prev = node; head = node; }else{ /* put the middle node as a head*/ node->prev->next = node->next; node->next->prev = node->prev; node->next = head; node->prev = nullptr; head->prev = node; head = node; } } }else{ /* no change in order*/ } } }

    virtual int get(int key)override{
        int value = -1;
        map<int,Node*>::iterator it = mp.find(key);
        if(it != mp.end()){
            value = it->second->value;
            Node* node = it->second;
            if(node != head){
                if(head->next == tail){
                    /* replace the order for head and tail*/
                    head = head->next;
                    tail =  tail->prev;
                    tail->next = nullptr;
                    head->prev = nullptr;
                    head->next = tail;
                    tail->prev = head;
                }else{
                    if(node == tail){
                        /* put the tail as a head*/
                        tail = tail->prev;
                        tail->next = nullptr;
                        node->prev = nullptr;
                        node->next = head;
                        head->prev = node;
                        head = node;
                    }else{
                       /* put the middle node as a head*/
                       node->prev->next = node->next;
                       node->next->prev = node->prev;
                       node->next = head;
                       node->prev = nullptr; 
                       head->prev = node;
                       head = node;
                    }
                }
            }else{
                /* no change in order*/
            }
        }
        return value;
    }
    

    };

  • + 0 comments

    My solution - I'm not a professional c++ dev but this was fun

    class LRUCache : public Cache 
    {
        private:
            int capacity;
            void move_node_to_head(Node* node);
            void remove_node_from_tail(Node* node);
        public:
            LRUCache(int capacity);
            int get(int key);
            void set(int key, int value);
    };
    
    
    LRUCache::LRUCache(int capacity)
    {
        this->tail = nullptr;
        this->head = nullptr;
        this->capacity = capacity; 
    }
    
    
    int LRUCache::get(int key)
    {
        if (mp[key] == nullptr) {
            return -1;
        }
        int cache_entry = mp[key]->value;
        move_node_to_head(mp[key]);
        return cache_entry;
    }
    
    void LRUCache::move_node_to_head(Node* new_head_node)
    {
        // In case we are getting or setting a value at the head
        if (head == new_head_node) {
            return;
        }
    
        // IN case its the very first insert, we set head = tail
        if (tail == nullptr) {
            tail = new_head_node;
        }
        if (head == nullptr) {
            head = new_head_node;
            mp[new_head_node->key] = new_head_node;
            return;
        }
    
        if (tail->prev == nullptr) {
            tail->prev = head;
        }
    
        /**
         *  N1 -> next | prv <- N2 -> next 
         * We take the currrent head and move it to the next position, so the new head node next, will point to the current head node previous node
         */
        new_head_node->next = head;   
        new_head_node->prev = nullptr; // A head doesn't have any previous node
        head = new_head_node;
    
      
        mp[new_head_node->key] = new_head_node;
    }
    
    
    /**
     * Need to remove the tail node and shifting the nodes to the right
     */
    void LRUCache::remove_node_from_tail(Node* node)
    {
        if (tail == nullptr) {
            return;
        }
        Node* old_tail = tail;
        if (tail->prev != nullptr) {
            tail->prev->next = nullptr; // remove the tail also from the node before
        }
       
        mp.erase(tail->key);
        delete old_tail;
    }
    
    
    void LRUCache::set(int key, int value)
    {
        Node* new_node = new Node(key, value);
    
        // first entry in the list
    
        if (mp[key] != nullptr) {
            // the Node is existing, so we update the value move to the head
            Node* node = mp[key];
            node->value = value;
            move_node_to_head(new_node);
        } else {
             // Cache is full
            if (mp.size() > this->capacity) {
                // remove node from tail
                remove_node_from_tail(new_node);
            }
            move_node_to_head(new_node);
        } 
    }