« back

LRU Cache

Tags : linkedlist, hashtable, geeksforgeeks, cpp, medium

Problem Statement - link #

Design a data structure that works like a LRU Cache. Here cap denotes the capacity of the cache and Q denotes the number of queries. Query can be of two types:

  1. SET x y : sets the value of the key x with value y
  2. GET x : gets the key of x if present else returns -1.

The LRUCache class has two methods get() and set() which are defined as follows.

  1. get(key) : returns the value of the key if it already exists in the cache otherwise returns -1.
  2. set(key, value) : if the key is already present, update its value. If not present, add the key-value pair to the cache. If the cache reaches its capacity it should invalidate the least recently used item before inserting the new item.
  3. In the constructor of the class the capacity of the cache should be intitialized.

Your Task: You don’t need to read input or print anything . Complete the constructor and get(), set() methods of the class LRUcache.

Expected Time Complexity: O(1) for both get() and set() Expected Auxiliary Space: O(1) for both get() and set() (Although, you may use extra space for cache storage and implementation purposes).

Examples #

Example 1:

Input:
cap = 2
Q = 2
Queries = SET 1 2 GET 1
Output: 2
Explanation: 
Cache Size = 2

SET 1 2 GET 1
SET 1 2 : 1 -> 2

GET 1 : Print the value corresponding
to Key 1, ie 2.

Example 2:

Input:
cap = 2
Q = 8
Queries = SET 1 2 SET 2 3 SET 1 5
SET 4 5 SET 6 7 GET 4 SET 1 2 GET 3
Output: 5 -1
Explanation: 
Cache Size = 2
SET 1 2 : 1 -> 2

SET 2 3 : 1 -> 2, 2 -> 3 (the most recently 
used one is kept at the rightmost position) 

SET 1 5 : 2 -> 3, 1 -> 5

SET 4 5 : 1 -> 5, 4 -> 5 (Cache size is 2, hence 
we delete the least recently used key-value pair)

SET 6 7 : 4 -> 5, 6 -> 7 

GET 4 : Prints 5 (The cache now looks like
6 -> 7, 4->5)

SET 1 2 : 4 -> 5, 1 -> 2 
(Cache size is 2, hence we delete the least 
recently used key-value pair)

GET 3 : No key value pair having 
key = 3. Hence, -1 is printed.

Constraints #

Solutions #

class LRUCache
{
    private:
    struct Node 
    {
        int key;
        int value;
        Node* prev;
        Node* next;
        Node(int key1, int value1)
        {
            key = key1;
            value = value1;
        }
    };
    public:
    int capacity;
    int size;
    Node* head;
    Node* tail;
    unordered_map<int, Node*> map;

    //Constructor for initializing the cache capacity with the given value.
    LRUCache(int capacity) 
    {
        this->capacity = capacity;
        this->size = 0;
        this->head = NULL;
        this->tail = NULL;
    }
    // delete a node
    void delete_node(Node* node) {
        if (node->prev != NULL) {
            node->prev->next = node->next;
        }
        if (node->next != NULL) {
            node->next->prev = node->prev;
        }
        if (node == head) {
            head = node->next;
        }
        if (node == tail) {
            tail = node->prev;
        }
        delete node;
    }
    // insert a node at the beginning of the list
    void insert(Node* node) {
        if (head == NULL) {
            head = node;
            tail = node;
        } else {
            node->next = head;
            head->prev = node;
            head = node;
        }
    }
    // move a node to the beginning of the list
    void move_to_beginning(Node* node) {
        if (node == head) {
            return;
        }
        if (node->prev != NULL) {
            node->prev->next = node->next;
        }
        if (node->next != NULL) {
            node->next->prev = node->prev;
        }
        if (node == tail) {
            tail = node->prev;
        }
        node->next = head;
        node->prev = NULL;
        head->prev = node;
        head = node;
    }    
    //Function to return value corresponding to the key.
    int get(int key)
    {
        // your code here
        if (map.find(key) == map.end())
        {
            return -1;
        }
        Node* node = map[key];
        move_to_beginning(node);
        return node->value;
    }
    
    //Function for storing key-value pair.
    void set(int key, int value)
    {
        // your code here
        if (map.find(key) == map.end())
        {
            if (size == capacity)
            {
                map.erase(tail->key);
                delete_node(tail);
                size--;
            }
            Node* node = new Node(key, value);
            insert(node);
            map[key] = node;
            size++;
        }
        else
        {
            Node* node = map[key];
            node->value = value;
            move_to_beginning(node);
        }   
    }
};