LRU Cache

Design a chache system

LRU Cache

Problem

Design a data structure that works as a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(capacity): Create the cache with a positive size capacity.
• get(key): Return the value of the key if it exists. Otherwise, return -1.
• put(key, value): Update the value if the key exists. Otherwise, add the key-value pair. If the number of keys becomes bigger than capacity, remove the least recently used key.

Both get and put must run in O(1) average time.

Examples

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]

• put(1, 1): cache is {1=1}.
• put(2, 2): cache is {1=1, 2=2}.
• get(1): returns 1. Now key 2 is the least recently used.
• put(3, 3): the cache is full, so key 2 is removed. Cache is {1=1, 3=3}.
• get(2): returns -1, because key 2 was removed.
• put(4, 4): key 1 is the least recently used, so it is removed. Cache is {3=3, 4=4}.
• get(1): returns -1.
• get(3): returns 3.
• get(4): returns 4.

Constraints

• 1 <= capacity <= 3000
• 0 <= key <= 10^4
• 0 <= value <= 10^5
• At most 2 * 10^5 calls are made to get and put.

Main Idea

We need two things to be fast:

• Find a key quickly.
• Move a key to the "most recent" position, and remove the oldest key, quickly.

One data structure cannot do both. So we use two together:

• Hash Map: It maps each key to its node. This finds any key in O(1).
• Doubly Linked List: It keeps the keys in order of use. This lets us remove a node and add a node in O(1), because each node knows both its neighbors.

How the list is arranged

head <-> [most recent] <-> ... <-> [least recent] <-> tail

• Nodes near head were used recently.
• The node just before tail is the least recently used.
• head and tail are fake nodes. They never hold data. They help us avoid special cases for an empty list or the first and last node.

Rules

• Using a key (get or put): Remove its node from the list, and add it right after head. It is now the most recent.
• Adding a new key beyond capacity: Remove the node right before tail. Also delete its key from the map.

Why does the node store its key? When we evict the last node, we only have the node. We need its key to delete it from the map.

Solution: Hash Map + Doubly Linked List

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

        // fake nodes at both ends
        this.head = {};
        this.tail = {};

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

    get(key) {
        // key is not in the cache
        if (!this.map.has(key)) return -1;

        let node = this.map.get(key);

        // move the node to the front (most recent)
        this.remove(node);
        this.add(node);

        return node.value;
    }

    put(key, value) {
        // key already exists: update it and move it to the front
        if (this.map.has(key)) {
            let node = this.map.get(key);
            node.value = value;

            this.remove(node);
            this.add(node);
            return;
        }

        // new key: create a node and add it to the front
        let node = { key, value };
        this.map.set(key, node);
        this.add(node);

        // too many keys: remove the least recently used one
        if (this.map.size > this.capacity) {
            let lru = this.tail.prev;

            this.remove(lru);
            this.map.delete(lru.key);
        }
    }

    // take a node out of the list
    remove(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // put a node right after head
    add(node) {
        node.next = this.head.next;
        node.prev = this.head;

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

How the Code Works

The constructor

• capacity is the maximum number of keys.
• map finds a node by its key.
• head and tail are fake nodes. We link them to each other, so the empty list is head <-> tail.

The helper remove(node)

• It connects the node's left neighbor directly to its right neighbor.
• The node is now out of the list. It takes O(1), because we do not search.

The helper add(node)

• It puts the node right after head.
• The steps are:
  • Point the node's next to the old first node.
  • Point the node's prev to head.
  • Point the old first node's prev back to the node.
  • Point head.next to the node.
• The order matters. We use this.head.next before we change it.

The method get(key)

• If the key is not in the map, return -1.
• Otherwise, move the node to the front, because it was just used, and return its value.

The method put(key, value)

• Key exists: Update the value and move the node to the front.
• Key is new:
  • Create the node, save it in the map, and add it to the front.
  • If the size is now bigger than capacity, take this.tail.prev. It is the least recently used node. Remove it from the list and from the map.

Dry Run

Let us use capacity = 2. We write the list from most recent to least recent.

The outputs are 1, -1, -1, 3, 4, the same as the example.

Complexity

• Time Complexity: O(1) for both get and put
  • Map operations (has, get, set, delete) take O(1) on average.
  • remove and add only change a few pointers.
  • We never loop through the list.
• Space Complexity: O(capacity)
  • The map and the list each hold at most capacity nodes (plus one temporary extra node during put).

Shorter Version (Optional)

A JavaScript Map remembers the order in which keys were added. So we can use it alone. To make a key "most recent", we delete it and add it again. The first key in the map is the least recently used.

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

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

        let value = this.map.get(key);

        // delete and set again to make it the most recent
        this.map.delete(key);
        this.map.set(key, value);

        return value;
    }

    put(key, value) {
        if (this.map.has(key)) {
            this.map.delete(key);
        }

        this.map.set(key, value);

        // remove the oldest key (the first one in the map)
        if (this.map.size > this.capacity) {
            let oldest = this.map.keys().next().value;
            this.map.delete(oldest);
        }
    }
}

• It is short and works well in practice, and its operations take O(1) on average.
• In interviews, the Map + Doubly Linked List version is the expected answer. It shows that you know how the data structure works inside.

Comparison

Summary

• An LRU cache needs fast lookup and fast reordering. So we combine two structures.
• The hash map finds a node by key in O(1).
• The doubly linked list keeps the use order. The front is the most recent, and the node before tail is the least recent.
• Fake head and tail nodes remove special cases.
• Every get or put of an existing key moves its node to the front.
• When the size goes over capacity, we remove tail.prev from both the list and the map. The node stores its key for this reason.
• Both get and put run in O(1) time, and the cache uses O(capacity) space.