LRU Cache

An LRU (Least Recently Used) Cache is a data structure that stores a limited number of items and automatically removes the least recently used item when the cache reaches its capacity. It's commonly used in scenarios where you need to manage memory by caching results of expensive operations.

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 a positive size capacity.
• int get(int key) returns the value of the key if it exists in the cache, otherwise returns -1.
• void put(int key, int value) updates the value of the key if it exists. Otherwise, adds the key-value pair to the cache. If the number of keys exceeds the capacity, evict the least recently used key.

Example

Using Ordered Map

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
    }

    get(key) {
        if (!this.cache.has(key)) return -1;

        const value = this.cache.get(key);
        // Refresh the key by deleting and re-adding it, moving it to the end of the Map
        this.cache.delete(key);
        this.cache.set(key, value);

        return value;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            // If the key already exists, delete it to refresh its position
            this.cache.delete(key);
        } else if (this.cache.size === this.capacity) {
            // If the cache is at capacity, remove the least recently used key (the first one)
            const firstKey = this.cache.keys().next().value;
            this.cache.delete(firstKey);
        }
        // Add the new key-value pair to the end of the Map
        this.cache.set(key, value);
    }
}

Using Doubly LinkedList

class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    moveToFront = (node) => {
        node.next = this.head.next;
        node.next.prev = node;
        this.head.next = node;
        node.prev = this.head;
    };
    removeNode = (node) => {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    };
    move2Front = (node) => {
        this.removeNode(node)
        this.moveToFront(node)
    }
    getTail = () => this.tail.prev;
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
        this.list = new DoublyLinkedList();
    }
    get = (key) => {
        if (!this.cache.has(key)) return -1;
        const node = this.cache.get(key);
        this.list.move2Front(node);
        return node.value;
    };
    put = (key, value) => {
        if (this.cache.has(key)) {
            const node = this.cache.get(key);
            node.value = value;
            this.list.move2Front(node);
        } else {
            if (this.cache.size >= this.capacity) {
                const tailNode = this.list.getTail();
                this.list.removeNode(tailNode);
                this.cache.delete(tailNode.key);
            }
            const newNode = new Node(key, value);
            this.list.moveToFront(newNode);
            this.cache.set(key, newNode);
        }
    };
}

Complexity Analysis

• Time Complexity: O(1) for both get and put operations. Access and updating the cache is constant time because of the hash map and linked list.
• Space Complexity: O(capacity) for storing key-value pairs in the cache and the nodes in the linked list.