LRU Caching | leetcode 146 | solution #1

Introduction

In computing, a caching algorithm is a way to optimize instructions for a software program or hardware device.

A Cache is a temporary storage. Reading from Cache takes less time than going all over the network again and again. But the Cache has limited memory.

The least recently used (LRU) is a caching algorithm. A basic caching mechanism discards the oldest items when the cache runs out of space. However, this can be inefficient in some cases. LRU is a more sophisticated approach that discards items that were not recently accessed.

Real-life examples:

1. Web Browsers: Web browsers store recently accessed web pages, images, and other resources locally to speed up the browsing experience. When the cache reaches its limit, the least recently accessed resources are removed to make space for new ones.
2. Operating Systems: Operating systems use caching to store recently accessed files and data in memory to improve performance.
3. Database Management Systems: Database management systems often use caching to store frequently accessed data in memory to reduce the number of disk reads.
4. CPU Caches: Modern processors use various levels of caches (L1, L2, L3) to store frequently accessed instructions and data to reduce memory access latency. LRU cache replacement policies are commonly used in CPU caches to determine which cache lines to evict when new data needs to be loaded.
5. Content Delivery Networks (CDNs): CDNs use caching to store copies of web content (such as images, videos, and scripts) at edge servers located closer to end users.

Implementing LRU cache

Let’s take leetcode problem #146 to understand the implementation of the LRU cache.

This problem can be solved by two different data structures.

1. HashMap.
2. Doubly Linked List + HashMap.

Problem statement

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with a 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.

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

The question is asking for the O(1) operations, which should direct your attention to the HashMap that provides the get and put in the constant time.

Solution #1 — HashMap

LRUCache(int capacity)Create a hashmap and single capacity variable to trace the length of the hashmap.

var LRUCache = function (capacity) {
    this.map = new Map();
    this.capacity = capacity;
};

int get(int key) First, check if a value exists or not if it does not exist return -1 else if it exits then we will add.

We will not simply add but we have to update the recently used value in the hashmap, which we will do by deleting and adding the value again.

Which shifts the position of value and adds value at the last index of the hashmap that denotes it’s recently used.

LRUCache.prototype.get = function (key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, val);
    return val;
};

void put(int key, int value) In the put call, we delete the existing value and add it again.

Which shifts the position of value and adds value at the last index of the hashmap that denotes it’s recently used.

After, we have to check for its capacity also if the hashmap length exceeds more than the given capacity then we simply delete the first items of the hashmap which is not recently used.

LRUCache.prototype.put = function (key, value) {
    this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
        const firstItem = this.map.keys().next().value;
        this.map.delete(firstItem);
    }
};

Complexity

• Time complexity: O(1)
• Space complexity: O(capacity)

Code

Solution #2 — Doubly Linked List

1. Create a Node class with attributes key, val, prev, and next to represent individual nodes of a doubly linked list.

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

2. We need a Doubly Linked List class that supports push and remove operations.

class DoublyLinkedList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    push(key, val) {
        const newNode = new Node(key, val);
        if (!this.head) {
            this.head = newNode;
            this.tail = newNode;
        } else {
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
        this.length++;
        return newNode;
    }

    remove(node) {
        if (!node.next && !node.prev) { // if there's only 1 node
            this.head = null;
            this.tail = null;
        } else if (!node.next) { // if the node is tail node
            this.tail = node.prev;
            this.tail.next = null;
        } else if (!node.prev) { // if the node is head node
            this.head = node.next;
            this.head.prev = null;
        } else { // if the node is in between
            const prev = node.prev;
            const next = node.next;
            prev.next = next;
            next.prev = prev;
        }
        this.length--;
    }
}

3. Implement the LRUCache class with a Doubly Linked List and Hashmap solution.

LRUCache class constructor()Create a Doubly Linked List and Hashmap and single capacity variable to trace the length of the hashmap.

int get(int key) First, check if a value exists or not if it does not exist return -1 else if it exits then we will add.

here also we will remove the existing value from the doubly linked list and push back again at the end of the doubly linked list.

here hashmap is used to only provide searching operations in O(1).

void put(int key, int value) In the put call, we delete the existing value and add it again.

Also, check if the size of the doubly linked list exceeds the given capacity if it exceeds then pop the first node which is not frequently used.

class LRUCache {
    constructor(capacity) {
        this.DLL = new DoublyLinkedList();
        this.map = {};
        this.capacity = capacity;
    }

    get(key) {
        if (!this.map[key]) return -1;
        const value = this.map[key].val;
        this.DLL.remove(this.map[key]);
        this.map[key] = this.DLL.push(key, value);
        return value;
    }

    put(key, value) {
        if (this.map[key]) this.DLL.remove(this.map[key]);
        this.map[key] = this.DLL.push(key, value);
        if (this.DLL.length > this.capacity) {
            const currKey = this.DLL.head.key;
            delete this.map[currKey];
            this.DLL.remove(this.DLL.head);
        }
    }
}

Complexity

• Time complexity: O(1)
• Space complexity: O(capacity)

Code