algoadvance

Leetcode 146. LRU Cache

Problem Statement

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

• LRUCache(int capacity) Initializes 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.

Clarifying Questions

1. What should happen when we put a key that already exists?
   • The value associated with the key should be updated, and the key should be marked as the most recently used.
2. Can we assume all keys and values are integers?
   • Yes, for simplicity, assume all keys and values are integers.
3. Is the capacity of the cache fixed after initialization?
   • Yes, after initialization with a given capacity, the size of the cache is fixed.

No more clarifications needed. Let’s move on to the solution.

Strategy

The problem essentially requires the design of an LRU Cache with efficient get and put operations. To achieve O(1) average time complexity for these operations, we can use the following data structures:

1. Hash Map for O(1) access to cache items.
2. Doubly Linked List to keep track of the order of insertion and access to determine the least recently used item.

We will use a combination of these two data structures:

• Hash Map will map keys to nodes in the doubly linked list.
• Doubly Linked List will store the key-value pairs, with the most recent node at the head and the least recent node at the tail. This way, we can quickly remove the least recently used nodes.

Code

#include <unordered_map>
using namespace std;

class LRUCache {
private:
    struct DListNode {
        int key;
        int value;
        DListNode* prev;
        DListNode* next;
        DListNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };

    unordered_map<int, DListNode*> cacheMap;
    DListNode* head;
    DListNode* tail;
    int capacity;
    int size;

    void removeNode(DListNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void addToHead(DListNode* node) {
        node->next = head->next;
        node->next->prev = node;
        head->next = node;
        node->prev = head;
    }

    DListNode* removeTail() {
        DListNode* node = tail->prev;
        removeNode(node);
        return node;
    }

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        this->size = 0;
        head = new DListNode(0, 0);
        tail = new DListNode(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (cacheMap.find(key) == cacheMap.end()) {
            return -1;
        }
        DListNode* node = cacheMap[key];
        removeNode(node);
        addToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (cacheMap.find(key) != cacheMap.end()) {
            DListNode* node = cacheMap[key];
            node->value = value;
            removeNode(node);
            addToHead(node);
        } else {
            DListNode* newNode = new DListNode(key, value);
            cacheMap[key] = newNode;
            addToHead(newNode);
            size++;
            if (size > capacity) {
                DListNode* tail = removeTail();
                cacheMap.erase(tail->key);
                delete tail;
                size--;
            }
        }
    }

    ~LRUCache() {
        DListNode* current = head;
        while (current) {
            DListNode* next = current->next;
            delete current;
            current = next;
        }
    }
};

Time Complexity

• get(int key): O(1) because we use the hash map to find the node and the doubly linked list to update its position.
• put(int key, int value): O(1) as well. Inserting a new node or updating an existing node’s position in the list involves a constant amount of work.

The solution efficiently handles the constraints and requirements of an LRU Cache.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?