hard

LRU Cache

Combine a hash map with a doubly linked list so reads, writes and throwing out the oldest entry are all fast.

1. Define the problem

LRU Cache

Build a cache that holds a fixed number of key-value pairs. When it is full and a new key arrives, throw out the least recently used pair — the one nobody has read or written for the longest time. Reading a missing key answers -1. Both reading and writing must take about the same small amount of time no matter how big the cache is. So that the input stays easy to read, this exercise takes the capacity plus a list of operations such as ["put", 1, 1] and ["get", 1], and returns an array holding the answer to each read, in order. The trick is to use two structures at once: a hash map to find any key instantly, and a doubly linked list to keep the pairs in order of how recently they were touched, so the throwaway candidate is always sitting at the back.

Constraints

  • 1 ≤ capacity ≤ 3000
  • 0 ≤ key ≤ 104 and 0 ≤ value ≤ 105
  • Up to 2 × 105 operations may be performed
  • Each get and each put must take about constant time

Example

Inputcapacity = 2, operations = [["put", 1, 1], ["put", 2, 2], ["get", 1], ["put", 3, 3], ["get", 2]]
Output[1, -1]

Explanation Reading key 1 answers 1 and makes it the most recent. Adding key 3 fills the cache, so key 2 — now the least recently used — is thrown out, and reading it answers -1.

2. Know the words first

In plain terms

Cache
A small store that keeps recent answers so they do not have to be worked out again. It has limited room, so old entries must sometimes be dropped.
Least recently used
The entry that has gone the longest without being read or written. It is the one thrown out when room is needed.
Doubly linked list
A chain where every node points both forwards and backwards. The backwards link is what lets you unhook a node from the middle without walking to it from the front.
Hash map
A lookup table from key to value. Here it maps a key straight to its node in the chain, so no searching is needed.
Head and tail guards
Two throwaway nodes pinned at each end of the chain. With them, every real node always has a neighbour on both sides, so inserting and unhooking never need special cases.
3. Visualize the solution

Two cells: the most recently used entry and the least recently used entry

Two cells: the most recently used entry and the least recently used entry
Statusput

put(1, 1) stores key 1 and puts it at the front; the cache holds one entry.

What happens in this step

capacity = 2
cache front = key1=1
cache back = nothing yet

A new node is created and hooked in right behind the head guard.
Step 1 of 8

Steps to visualize

  1. The left cell is the front of the chain, the entry touched most recently.
  2. The right cell is the back of the chain, the entry that would be thrown out next.
  3. Every get and every put moves the entry it touched to the front.
  4. When the cache is full, a new key removes whatever sits at the back.
  5. A get on a key that is no longer there answers -1.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Two cells: the most recently used entry and the least recently used entry
Statusput

put(1, 1) stores key 1 and puts it at the front; the cache holds one entry.

What happens in this step

capacity = 2
cache front = key1=1
cache back = nothing yet

A new node is created and hooked in right behind the head guard.
Step 1 of 8
5. Solution

Solution

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

function lruCache(capacity, operations) {
  const map = new Map();
  const head = new Node(0, 0);
  const tail = new Node(0, 0);
  head.next = tail;
  tail.prev = head;

  function unhook(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  function addFront(node) {
    node.next = head.next;
    node.prev = head;
    head.next.prev = node;
    head.next = node;
  }

  const results = [];

  for (const op of operations) {
    if (op[0] === 'get') {
      const found = map.get(op[1]);
      if (found === undefined) {
        results.push(-1);
      } else {
        unhook(found);
        addFront(found);
        results.push(found.value);
      }
    } else {
      const existing = map.get(op[1]);
      if (existing !== undefined) {
        existing.value = op[2];
        unhook(existing);
        addFront(existing);
      } else {
        if (map.size === capacity) {
          const last = tail.prev;
          unhook(last);
          map.delete(last.key);
        }
        const node = new Node(op[1], op[2]);
        map.set(op[1], node);
        addFront(node);
      }
    }
  }

  return results;
}
Time
O(1) per operation
Space
O(capacity)
6. Test cases

Test cases

InputExpectedCovers
capacity = 2, operations = [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]][1, -1, -1, 3, 4]the classic run, including two entries being thrown out
capacity = 1, operations = [["put",1,1],["get",1],["put",2,2],["get",1],["get",2]][1, -1, 2]smallest cache, where every new key throws out the old one
capacity = 2, operations = [["get",5]][-1]reading from a cache that holds nothing
capacity = 2, operations = [["put",1,1],["put",1,10],["get",1]][10]writing a key that already exists replaces its value without adding an entry
capacity = 2, operations = [["put",1,1],["put",2,2],["put",1,5],["put",3,3],["get",2],["get",1],["get",3]][-1, 5, 3]writing an existing key also makes it recent, so a different key is dropped
capacity = 3, operations = [["put",1,1],["put",2,2],["put",3,3],["get",1],["put",4,4],["get",2],["get",3],["get",4],["get",1]][1, -1, 3, 4, 1]a longer run where a read saves a key from being thrown out

Keep reading