leetcode Question: LRU Cache

LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Analysis:


This a more likely a design question other than a algorithm question, which requires us to choose the proper data structure and implement the "get", "set" methods.

At the first glance, a queue seems enough for this problem, because of its FIFO property. However,  the questions also requires "Recently", which means both "input" and "visit" are "recent actions" for the data. If you have the data "<1,1>"  the least recently used element in the queue <1,1> <2,2><3,3>, if method "get(1)" is called, "<1,1>" is now becoming the last (recently used) element in the queue. (<2,2,><3,3,><1,1>)

Consider the basic operations we need:
(1) Insert a new <key, value> pair to the end of the list.
(2) delete a <key, value> pair (if the cache is full).
(3) move a <key, value> pair to the end. (when it is used)
(3) change the value in a <key, value> pair and move it to the end.

Therefore,  a double linked list can handle the above methods well. A map<key, node*>  is a good way tracking the position of the node according to its key.

Be careful with the following cases:
(1) List is empty
(2) List has one node
(3) Initialization
(4) Don't forget delete the element in the map when it is removed from list.


Code:


class LRUCache{
  
//define the double linked list, each node stores both the key and value.
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){};
};


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



public:
    //constructor
    LRUCache(int capacity) {
        cp = capacity;
        mp.clear();
        head=NULL;
        tail=NULL;
    }
    
    //insert node to the tail of the linked list
    void insertNode(Node* node){
        if (!head){
            head = node;
            tail = node;
        }else{
            tail->next = node;
            node->prev = tail;
            tail = tail->next;
        }
    }

    //remove current node
    void rmNode(Node* node){
        if (node==head){
            head = head->next;
            if (head){head->prev = NULL;}
        }else{
            if (node==tail){
                tail =tail->prev;
                tail->next = NULL;
            }else{
                node->next->prev = node->prev;
                node->prev->next = node->next;
            }
        }
    }

    // move current node to the tail of the linked list
    void moveNode(Node* node){
        if (tail==node){
            return;
        }else{
            if (node==head){
                node->next->prev = NULL;
                head = node->next;
                tail->next = node;
                node->prev = tail;
                tail=tail->next;
            }else{
                node->prev->next = node->next;
                node->next->prev = node->prev;
                tail->next = node;
                node->prev = tail;
                tail=tail->next;
            }
        }
    }


    ///////////////////////////////////////////////////////////////////////
    // get method
    ///////////////////////////////////////////////////////////////////////
    int get(int key) {
        if (mp.find(key)==mp.end()){
            return -1;
        }else{
            Node *tmp = mp[key];
            moveNode(tmp);
            return mp[key]->value;
        }
    }

    ///////////////////////////////////////////////////////////////////////
    // set method
    ///////////////////////////////////////////////////////////////////////
    void set(int key, int value) {
        if (mp.find(key)!=mp.end()){
            moveNode(mp[key]);
            mp[key]->value = value;
        }else{
            if (mp.size()==cp){
                mp.erase(head->key);
                rmNode(head);
            }
            Node * node = new Node(key,value);
            mp[key] = node;
            insertNode(node);
        }
    }
};

5 comments:

  1. Hello Yu! I am just wondering if tail should also be dealt with in line 44-46. If there is only one node in the list, which is head==tail, after we remove it(head), we should set tail = NULL. Please correct me if I am wrong with it.

    ReplyDelete
  2. Do you need to remove space since you Node * node = new Node(key,value);
    but no deletion?

    ReplyDelete
    Replies
    1. +1. And if the capacity==0, the program will crash if set operation is called.

      Delete
  3. This comment has been removed by the author.

    ReplyDelete
  4. Hey,I made a video explaining the solution using doubly linked list and hashmap, you can check this out !!
    Please do subscribe if you find this helpful
    https://www.youtube.com/watch?v=uIojskB-xAo

    ReplyDelete