Abstract Classes - Polymorphism Discussions | C++

Sort by

recency

|

330 Discussions

|

3 weeks ago+ 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

1 month ago+ 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;
        }
};

1 month ago+ 0 comments

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

6 months ago+ 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;
}

};

7 months ago+ 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);
    } 
}

Sort by

|

330 Discussions

|

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge