LRU cache (IMPORTANT)

Dec 18, 2024 • 6 mins read

Problem Overview

The problem at hand is implementing an LRU (Least Recently Used) Cache. This is a classic example of a cache system where the least recently used items are discarded first when space is needed for new items. The system should support the following operations efficiently:

get(key): Retrieve the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value): Update the value of the key if it exists. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The key challenge here is to design the cache to maintain these operations with good performance.

Understanding the Problem

The LRU Cache problem is a design problem where you need to balance between maintaining a limit on the cache size and ensuring that retrieval and updates are fast. The cache should discard the least recently used items first to make room for new data. Hence, the data structure chosen must support fast insertion, deletion, and access, with an understanding of usage order.

Example

Let's assume a cache of capacity 2:

put(1, 1) - The cache is now: {1=1}
put(2, 2) - The cache is now: {1=1, 2=2}
get(1) - Returns 1, cache becomes: {2=2, 1=1}
put(3, 3) - Evicts key 2, adding key 3, cache becomes: {1=1, 3=3}
get(2) - Returns -1 (not found)
put(4, 4) - Evicts key 1, adding key 4, cache becomes: {3=3, 4=4}
get(1) - Returns -1 (not found)
get(3) - Returns 3
get(4) - Returns 4

Key DSA Concepts and Theory

Double-Linked List

A double-linked list allows traversal in both directions and efficient insertion/deletion from both ends, which is useful in maintaining the order of access.

Node structure: Each node contains a key, value, a pointer to the next node, and a pointer to the previous node.

Hash Map

A hash map provides O(1) average time complexity for search operations. It is used to maintain a map of key to the corresponding node in the linked list, thus allowing O(1) access to any node by key.

Least Recently Used (LRU) Policy

The LRU policy requires removing the least recently used (not recently accessed or modified) item first. This needs tracking the order of item usage, which is efficiently administered by the combination of the hash map and the double-linked list.

Solution Approach

The solution involves combining a hash map and a double-linked list. Here's a detailed breakdown of the approach:

Data Structure Design:
- A HashMap (in Java) or unordered_map (in C++) will store the keys and will map to corresponding nodes in a Doubly Linked List.
- The Doubly Linked List will keep track of the order of the nodes where the node at the head is the most recently used and the one at the tail is the least recently used.
Operation Implementation:
- get(key): Check if the key exists in the map. If it does, move the node to the head of the list and return its value. If not, return -1.
- put(key, value): Check if the key exists.
  - If it exists, update its value and move it to the head of the list.
  - If it does not exist, add a new node. If the cache exceeds capacity, remove the node at the tail of the list, then add the new node to the head.
Edge Cases:
- Cache of size 0 should handle requests without error.
- Consecutive put with the same key should place the key at the head but maintain logical consistency.

C++ Code Implementation

#include <unordered_map>

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

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

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

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

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

public:
    LRUCache(int capacity) : capacity(capacity), size(0) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        Node* node = cache[key];
        removeNode(node);
        addToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            Node* node = cache[key];
            node->value = value;
            removeNode(node);
            addToHead(node);
        } else {
            Node* newNode = new Node(key, value);
            cache[key] = newNode;
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                Node* tail = removeTail();
                cache.erase(tail->key);
                delete tail;
                --size;
            }
        }
    }
};

Java Code Implementation

import java.util.HashMap;

class LRUCache {
    private class Node {
        int key;
        int value;
        Node prev;
        Node next;
    }

    private void addNode(Node node) {
        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        Node prev = node.prev;
        Node next = node.next;

        prev.next = next;
        next.prev = prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addNode(node);
    }

    private Node popTail() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }

    private HashMap<Integer, Node> cache = new HashMap<>();
    private int size;
    private int capacity;
    private Node head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;

        head = new Node();
        tail = new Node();

        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) return -1;

        moveToHead(node);

        return node.value;
    }

    public void put(int key, int value) {
        Node node = cache.get(key);

        if (node == null) {
            Node newNode = new Node();
            newNode.key = key;
            newNode.value = value;

            cache.put(key, newNode);
            addNode(newNode);

            ++size;

            if (size > capacity) {
                Node tail = popTail();
                cache.remove(tail.key);
                --size;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }
}

Time and Space Complexity Analysis

Time Complexity:
- Both get and put operations have a time complexity of O(1). This is made possible by the combination of the hash map (for fast access) and the doubly linked list (for quick removals and additions).
Space Complexity:
- The space complexity is O(capacity) to hold the keys, values, and pointers in the doubly linked list and hash map.

Common Mistakes to Avoid

Forgetting to Update the Node Position in get: Ensure that during the get operation, the element is moved to the head of the linked list.
Handling Edge Cases for Single Element Capacity: Properly handle operations when the cache capacity changes or is minimal.
Memory Management in C++: Ensure no memory leaks by managing dynamic memory allocation and deallocation well in C++ implementations.

Additional Resources and References

This article provides a thorough understanding of how to implement an LRU Cache using key data structures like hash maps and doubly linked lists, ensuring efficient performance for both get and put operations.

Terms & Conditions Privacy Policy Refund Policy