Lru Cache - Leetcode Solution

The LRU Cache problem on LeetCode is a popular algorithmic problem that involves designing an efficient data structure that supports two operations - get and put. The data structure should be able to store a fixed number of key-value pairs and should satisfy the following conditions:

1. If a key is already present in the cache, its corresponding value should be updated (since we are considering the most recently used value), and it should be moved to the front of the cache.

2. If a key is not present in the cache, it should be added to the cache and moved to the front of the cache. If the cache is full, the least recently used key-value pair should be removed from the cache to make space for the new key-value pair.

To solve this problem, we can use a combination of a hash map and a doubly linked list. The hash map will map each key to its corresponding node in the doubly linked list. The doubly linked list will maintain the order in which the keys were last accessed, with the most recently used key at the front of the list and the least recently used key at the end of the list.

Here is the step-by-step solution to the LRU Cache problem:

Step 1: Define a doubly linked list node class that stores the key and value of each key-value pair in the cache, as well as pointers to the previous and next nodes in the list.

class Node {
public:
    int key;
    int value;
    Node* prev;
    Node* next;
    Node(int key, int value): key(key), value(value), prev(nullptr), next(nullptr) {}
};

Step 2: Define a hash map that maps keys to their corresponding nodes in the doubly linked list.

unordered_map<int, Node*> cacheMap;

Step 3: Define a doubly linked list that maintains the order in which the keys were last accessed.

class LRUCache {
    int capacity;
    Node* head;
    Node* tail;
public:
    LRUCache(int capacity): capacity(capacity), head(nullptr), tail(nullptr) {}
};

Step 4: Implement the get method that retrieves the value of a key from the cache. If the key is not present in the cache, return -1. If the key is present in the cache, move its corresponding node to the front of the list and return its value.

int get(int key) {
    if (cacheMap.find(key) == cacheMap.end()) {
        // key not found in cache
        return -1;
    }
    // key found in cache
    Node* node = cacheMap[key];
    if (node != head) {
        // move node to front of list
        if (tail == node) {
            tail = node->prev;
        }
        node->prev->next = node->next;
        if (node->next != nullptr) {
            node->next->prev = node->prev;
        }
        node->prev = nullptr;
        node->next = head;
        head->prev = node;
        head = node;
    }
    return node->value;
}

Step 5: Implement the put method that adds a key-value pair to the cache. If the key is already present in the cache, update its value and move its corresponding node to the front of the list. If the key is not present in the cache, create a new node for the key-value pair and add it to the front of the list. If the cache is full, remove the least recently used key-value pair (i.e., the node at the end of the list) from the cache.

void put(int key, int value) {
    if (cacheMap.find(key) != cacheMap.end()) {
        // key already exists in cache, update value and move node to front of list
        Node* node = cacheMap[key];
        node->value = value;
        if (node != head) {
            // move node to front of list
            if (tail == node) {
                tail = node->prev;
            }
            node->prev->next = node->next;
            if (node->next != nullptr) {
                node->next->prev = node->prev;
            }
            node->prev = nullptr;
            node->next = head;
            head->prev = node;
            head = node;
        }
    } else {
        // key not found in cache, create new node and add to front of list
        Node* node = new Node(key, value);
        cacheMap[key] = node;
        if (head == nullptr) {
            head = tail = node;
        } else {
            node->next = head;
            head->prev = node;
            head = node;
        }
        if (cacheMap.size() > capacity) {
            // cache is full, remove least recently used node from end of list
            cacheMap.erase(tail->key);
            Node* prevTail = tail->prev;
            delete tail;
            tail = prevTail;
            if (tail != nullptr) {
                tail->next = nullptr;
            }
        }
    }
}

Step 6: Test the LRU Cache implementation by creating an instance of the LRUCache class and calling the get and put methods on it with various key-value pairs.

1