Design LRU cache LLD | CPP OOP used
Dhaval Prajapati
1661
Object-Oriented DesignSystem DesignLow Level Designinterview questionInterview

For LLD this question is frequently asked in interview start with below approach for any LLD.
( please upvote if you like and give suggestion in comment)

  1. Requirement Gathering ( make sure not miss match)
  2. try to think of extra features ( optional requirements )
  3. Write class name and methods

we will do all operation in O(1) explanation click here

For LRU cache here is my code :
we have 3 class

  1. Node class
    -> contain node attribute and we will use it in map and DLL
  2. Doublylinklist class writing our own DLL class so we can use API directly
  3. LRUCache class this is for main functionality
class Node
{
public:
    Node *prev, *next;
    int key, value; // key : pageid , value: memory location
    Node(int pageId, int mValue)
    {
        key = pageId;
        value = mValue;
        prev = NULL;
        next = NULL;
    }
    //TODO: gatter setter
};

DLL class


class DLL{
    Node *front, *rear;

public:
    DLL()
    {
        front = NULL;
        rear = NULL;
    }

    Node *addTohead(int pageId, int memoryValue)
    {
        Node *page = new Node(pageId, memoryValue);
        // if empty queue
        if (!front && !rear)
        {
            front = rear = page;
        }
        else
        {
            // add in the front
            page->next = front;
            front->prev = page;
            front = page;
        }
        return page;
    }

    void moveTohead(Node *page)
    {

        if (page == front) //if already on front
        {
            return;
        }
        if (page == rear) // if last then remove
        {
            rear = rear->prev;
            rear->next = NULL;
        }
        else
        {
            // delete in between
            page->prev->next = page->next;
            page->next->prev = page->prev;
        }
        //add in front
        page->next = front;
        page->prev = NULL;
        front->prev = page;
        front = page;
    }
    // when queue is full remove least recent
    void removeRear()
    {
        if (isEmpty())
        {
            return;
        }
        if (front == rear)
        {
            delete rear;
            front = rear = NULL;
        }
        else
        {
            rear = rear->prev;
            rear->next = NULL;
        }
    }
    Node *getLastPage()
    {
        return rear;
    }

    bool isEmpty()
    {
        if (rear == NULL)
            return true;
        return false;
    }
};

LRU cache class

class LRUCache {
public:
    int capacity;
    map<int,Node*> mp;
    int filledSize;
    DLL *pageList;
    LRUCache(int capacity) {
            this->filledSize=0;
            this->capacity=capacity;
            pageList=new DLL();
    }
    
    int get(int key) {
        if(mp.find(key)==mp.end())
            return -1;
        int n=mp[key]->value;
         pageList->moveTohead(mp[key]);
        return n;
    }
    
    void put(int key, int value) {
        if(mp.find(key)!=mp.end()){
            pageList->moveTohead(mp[key]);
            mp[key]->value=value;
            return;
        }
        if(filledSize==capacity){
            int id=pageList->getLastPage()->key;
            mp.erase(id);
            pageList->removeRear();
            filledSize--;
        }
        filledSize++;
        Node* page= pageList->addTohead(key,value);
        mp[key]=page;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
Comments (3)