Leetcode Study Day 31

LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4
 

Constraints:

1 <= capacity <= 3000
0 <= key <= 104
0 <= value <= 105
At most 2 * 105 calls will be made to get and put.

Solution

The idea to implement an LRU cache with O(1) operations is to use a combination of a hash map (or dictionary) and a doubly-linked list:

Doubly-linked list: This ensures that the items can be added, removed, and moved to the front in O(1) time. The most recently accessed or added item is at the front, while the least recently accessed item is at the back.

Hash map: It’s used to achieve O(1) lookup times. The key will be the actual key of the cache, and the value will be a reference (or pointer) to the corresponding node in the doubly-linked list.

Full code:

class LRUCache {
    // initialise the node structure
    struct Node {
        int key, value;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };

    int capacity;
    std::unordered_map<int, Node*> map;
    Node *head, *tail;

    // Helper function to add a node after the head
    void add(Node* node) {
        node->next = head->next;
        head->next->prev = node;
        node->prev = head;
        head->next = node;
    }

    // Helper function to remove a node
    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

public:
    // initialise the LRUCahce, with two dummy nodes head and tail
    // The actual cached items lie between head and tail.
    LRUCache(int capacity) : capacity(capacity) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    // clean up the memory used by the doubly-linked list
    ~LRUCache() {
        while (head) {
            Node* temp = head->next;
            delete head;
            head = temp;
        }
    }

    int get(int key) {
        // if we find the key in the map
        if (map.find(key) != map.end()) {
            Node* node = map[key];
            // we remove and add the node to make sure the postion of the node is head->next
            remove(node);
            add(node);
            return node->value;
        }
        return -1;
    }

    void put(int key, int value) {
        // if we find the key in map, we delete the key and erase it in the map
        if (map.find(key) != map.end()) {
            remove(map[key]);
            delete map[key];
        }

        Node* node = new Node(key, value);
        add(node);
        map[key] = node;
        // if the amount of nodes is greater than that of capacity
        if (map.size() > capacity) {
            // the least recently used (LRU) item is the one right before the tail
            Node* lastNode = tail->prev;
            remove(lastNode);
            map.erase(lastNode->key);
            delete lastNode;
        }
    }
};


/**
 * 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);
 */