LRU Cache

The problem

Build a cache that stores values under keys, up to a fixed number of keys: its capacity. operations lists the operation names and values their arguments, in the same order. Run them in order and return the list of their results. "LRUCache" comes first, with the capacity, and gives null. "put" stores a value under a key, replacing any old value, and gives null; if the cache then holds too many keys, it drops the least recently used key, whose last use is longest ago. "get" gives a key's value, or -1 if the key is not stored. Every put, and every get that finds its key, is a use.

What to write

function solve(operations: string[], values: number[][]): (number | null)[]

Input
operations = ["LRUCache","put","put","get","put","get","put","get","get","get"]
values = [[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]

Input
operations = ["LRUCache","put","put","get","get"]
values = [[1],[1,2],[2,3],[1],[2]]

Output
[null,null,null,-1,3]

Constraints

Capacity is positive.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   A real cache can hold thousands of keys, so aim for every get and put to take about one step however full the cache is. That rules out searching all the keys for the one used longest ago. Remember too that a get which finds its key counts as a use, like every put.

2. Hint 2: Ask a smaller question

   Play the first example with paper cards, one card per key. Before each put, decide which card would have to go if the cache were full. Did you have to think back through the earlier operations to decide? What arrangement of the cards would make that choice instant?

3. Hint 3: Name the pattern

   The task lists operations, and each one should be fast: the sign of a purpose-built data structure. You need two abilities at once: finding a key in about one step, and moving it to the newest end of a row in about one step. A hash map gives the first, a doubly linked list the second. Read the lesson on purpose-built data structure.

4. Hint 4: State the invariant

   The list's order is always the order of last use: the entry after the start marker is the least recently used, the one before the end marker the most recently used. Every get that finds its key and every put must move that key's entry to the newest end.

5. Hint 5: Sketch the pseudocode

   Keep a hash map from key to entry, and the entries in a doubly linked list between two markers. get: if the key is stored, unlink its entry, link it in as the newest and answer its value; otherwise answer -1. put: unlink any old entry, link in a new one, then unlink the oldest if over capacity.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Keep a hash map from key to entry, and the entries in a doubly linked list ordered by last use. Every use moves its entry to the newest end; over capacity, the entry at the oldest end goes.

The slow way

Store with every key the time of its last use: a counter that goes up with each operation. When the cache is over capacity, look through all the keys for the oldest time and remove that key. It is correct, but each such removal looks at every key in the cache, so a put gets slower as the capacity grows.

The insight

You never need the times, only which key was used longest ago: the least recently used key. Keep the keys in a row ordered by last use: a key that is used moves to the newest end, so the least recently used is always at the oldest end. A doubly linked list moves an entry in one step, and a hash map finds the entry.

Step by step

1. Map each key to its entry; link the entries from oldest to newest. The map finds a key's entry in about one step. The list keeps the order of last use. Two markers that hold no key stand at its ends, so a real entry always has a neighbor on both sides.
2. To take an entry out, join its two neighbors to each other. An entry knows the entry before it and the entry after it. Pointing those two at each other removes it from the row in one step, wherever it stands.
3. To make an entry the newest, link it in before the end marker. The end marker's neighbor is the newest entry so far. The new entry goes between that one and the marker, which takes four links: two on the entry, one on each neighbor.
4. A get moves a stored key's entry to the newest end, or answers -1. Reading a key is a use, so its entry becomes the most recently used. The check asks whether the map holds the key: a stored 0 is still a value, and one of the tests stores 0.
5. A put drops any old entry for the key and links in a new newest one. Writing to a stored key is a use as well, so its old entry leaves its place in the row. The new entry carries the new value and goes to the newest end.
6. Over capacity: unlink the entry after the start marker, forget its key. Every use moved its entry to the newest end, so the entry next to the start marker was used longest ago. Its key must leave the map too, or a later get would still find it.
7. Add each result to the list; the full list is the answer. The judge compares one result per operation, in order. The constructor and every put left the result as null, and a get set it to a value or to -1.

The same numbered steps are the comments in each solution.

function solve(operations, values) {
  // 1. Map each key to its entry; link the entries from oldest to newest
  const entries = new Map();
  const capacity = values[0][0];
  // Two entries that hold no key stand at the two ends of the list. A real
  // entry then always has a neighbor on each side, so no step has to ask
  // whether it is the first or the last.
  const oldest = { key: 0, value: 0, prev: null, next: null };
  const newest = { key: 0, value: 0, prev: oldest, next: null };
  oldest.next = newest;
  // 2. To take an entry out, join its two neighbors to each other
  function unlink(entry) {
    entry.prev.next = entry.next;
    entry.next.prev = entry.prev;
  }
  // 3. To make an entry the newest, link it in before the end marker
  function linkNewest(entry) {
    entry.prev = newest.prev;
    entry.next = newest;
    newest.prev.next = entry;
    newest.prev = entry;
  }
  const out = [];
  for (let i = 0; i < operations.length; i++) {
    let result = null;
    if (operations[i] === "get") {
      // 4. A get moves a stored key's entry to the newest end, or answers -1
      const entry = entries.get(values[i][0]);
      if (entry) {
        unlink(entry);
        linkNewest(entry);
        result = entry.value;
      } else {
        result = -1;
      }
    } else if (operations[i] === "put") {
      // 5. A put drops any old entry for the key and links in a new newest one
      const [key, value] = values[i];
      const old = entries.get(key);
      if (old) unlink(old);
      const entry = { key, value, prev: null, next: null };
      entries.set(key, entry);
      linkNewest(entry);
      // 6. Over capacity: unlink the entry after the start marker, forget its key
      if (entries.size > capacity) {
        const first = oldest.next;
        unlink(first);
        entries.delete(first.key);
      }
    }
    // 7. Add each result to the list; the full list is the answer
    out.push(result);
  }
  return out;
}

type Entry = {
  key: number;
  value: number;
  prev: Entry | null;
  next: Entry | null;
};
function solve(operations: string[], values: number[][]): (number | null)[] {
  // 1. Map each key to its entry; link the entries from oldest to newest
  const entries = new Map<number, Entry>();
  const capacity = values[0][0];
  // Two entries that hold no key stand at the two ends of the list. A real
  // entry then always has a neighbor on each side, so no step has to ask
  // whether it is the first or the last.
  const oldest: Entry = { key: 0, value: 0, prev: null, next: null };
  const newest: Entry = { key: 0, value: 0, prev: oldest, next: null };
  oldest.next = newest;
  // 2. To take an entry out, join its two neighbors to each other
  function unlink(entry: Entry): void {
    entry.prev!.next = entry.next;
    entry.next!.prev = entry.prev;
  }
  // 3. To make an entry the newest, link it in before the end marker
  function linkNewest(entry: Entry): void {
    entry.prev = newest.prev;
    entry.next = newest;
    newest.prev!.next = entry;
    newest.prev = entry;
  }
  const out: (number | null)[] = [];
  for (let i = 0; i < operations.length; i++) {
    let result: number | null = null;
    if (operations[i] === "get") {
      // 4. A get moves a stored key's entry to the newest end, or answers -1
      const entry = entries.get(values[i][0]);
      if (entry) {
        unlink(entry);
        linkNewest(entry);
        result = entry.value;
      } else {
        result = -1;
      }
    } else if (operations[i] === "put") {
      // 5. A put drops any old entry for the key and links in a new newest one
      const [key, value] = values[i];
      const old = entries.get(key);
      if (old) unlink(old);
      const entry: Entry = { key, value, prev: null, next: null };
      entries.set(key, entry);
      linkNewest(entry);
      // 6. Over capacity: unlink the entry after the start marker, forget its key
      if (entries.size > capacity) {
        const first = oldest.next!;
        unlink(first);
        entries.delete(first.key);
      }
    }
    // 7. Add each result to the list; the full list is the answer
    out.push(result);
  }
  return out;
}

class Entry:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


def solve(operations, values):
    # 1. Map each key to its entry; link the entries from oldest to newest
    entries = {}
    capacity = values[0][0]
    # Two entries that hold no key stand at the two ends of the list. A real
    # entry then always has a neighbor on each side, so no step has to ask
    # whether it is the first or the last.
    oldest = Entry(0, 0)
    newest = Entry(0, 0)
    oldest.next = newest
    newest.prev = oldest

    # 2. To take an entry out, join its two neighbors to each other
    def unlink(entry):
        entry.prev.next = entry.next
        entry.next.prev = entry.prev

    # 3. To make an entry the newest, link it in before the end marker
    def link_newest(entry):
        entry.prev = newest.prev
        entry.next = newest
        newest.prev.next = entry
        newest.prev = entry

    out = []
    for op, args in zip(operations, values):
        result = None
        if op == "get":
            # 4. A get moves a stored key's entry to the newest end, or answers -1
            entry = entries.get(args[0])
            if entry:
                unlink(entry)
                link_newest(entry)
                result = entry.value
            else:
                result = -1
        elif op == "put":
            # 5. A put drops any old entry for the key and links in a new newest one
            key, value = args
            if key in entries:
                unlink(entries[key])
            entry = Entry(key, value)
            entries[key] = entry
            link_newest(entry)
            # 6. Over capacity: unlink the entry after the start marker, forget its key
            if len(entries) > capacity:
                first = oldest.next
                unlink(first)
                del entries[first.key]
        # 7. Add each result to the list; the full list is the answer
        out.append(result)
    return out

Example 1, traced

Input
operations = ["LRUCache","put","put","get","put","get","put","get","get","get"]
values = [[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]

Why it works

The list always holds the stored keys from least to most recently used. That holds for the empty list, and each get or put moves only the entry it uses to the newest end and leaves the others in their order. So the entry next to the start marker is always the one used longest ago, which is the key the rules say to drop.

Time and space

Time O(1) average per operation, extra space O(capacity). A get or put does one map lookup and changes a handful of links, whatever the number of stored keys: O(1) per operation, on average for the map. The map and the list hold at most capacity + 1 keys at any moment: O(capacity) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• A get is a use too. If only put moves a key to the newest end, storing key 3 in the first example drops key 1 instead of key 2, and the get for key 2 answers 2, not -1.
• Writing to a stored key is a use. With capacity 2, store keys 1 and 2, write key 1 again and store key 3: key 2 must go. If the write leaves key 1's entry in place, key 1 goes.
• Unlinking the oldest entry is half the job: its key must leave the map too. Otherwise a get still finds it: in the first example the gets for keys 2 and 1 answer 2 and 1, not -1.

Pattern

Purpose-built data structure. Builds on Two Sum and Min Stack.

Keep going