Skip to content

Volume ITechnology

4.9.9 — LRU Cache ​

LeetCode 146 · Medium · ★ Blind 75

The problem ​

Design a cache with a fixed capacity. A cache is a small, fast store that keeps recently used data close at hand, so you do not have to fetch it from somewhere slow again. This one must support two operations, both in O(1) time.

  • get(key) returns the value stored for key, or −1 if the key is not there. Reading a key counts as using it.
  • put(key, value) stores the value. If the key already exists, its value is updated. If storing it makes the cache hold more than capacity keys, throw out the least recently used key. That is what LRU stands for.
LRUCache(2)          capacity 2
put(1, 1)            cache: {1}
put(2, 2)            cache: {1, 2}
get(1)   → 1         1 is now the most recently used
put(3, 3)            too many keys: throw out 2, the least recently used
get(2)   → -1        2 is gone
get(3)   → 3

The capacity is up to 3,000, and there are up to 200,000 calls.

What the problem is really asking ​

Think of browser tabs, with room for only a few. When you open a new tab and you are at the limit, the browser closes the tab you have not looked at for the longest time. When you click an old tab, it becomes the most recently used again.

Two jobs pull in different directions.

  1. Find a key instantly. That is what a hash map does. But a hash map has no idea which key was used longest ago.
  2. Keep the keys in order of use, and move any key to the "most recent" end instantly. An ordered list does that. But finding a key in a list means walking it.

So the real question is: how do you get instant lookup and instant reordering at the same time?

The brute force, and where it wastes work ​

Keep a list of keys in order of use, most recent first, alongside a map of values. On get, find the key in the list, remove it, and put it at the front.

Finding a key in a list, and removing it from the middle, both take O(n), because the items after it have to shift along. With 200,000 calls and a capacity of 3,000, that is hundreds of millions of steps.

The waste in one sentence: every use shifts a list to move one key, when a linked list could unhook that key and re-hook it at the front by changing four pointers.

The idea ​

Use both structures, and let each cover the other's weakness.

  • A hash map from each key to a node. This gives O(1) lookup.
  • A doubly linked list of those nodes, in order of use: most recent at the front, least recent at the back. This gives O(1) reordering.

The map finds the node. The list knows the order. Saying this in one sentence is the whole point of the problem.

hash mapkey 3key 1key 2doubly linked list (order of use)head312tail⇄⇄⇄⇄most recentleast recent → evict next
Each map entry points straight at its node in the list. The node just before the tail dummy is always the one to throw out.

Read the figure in two parts. On the left, the hash map turns a key into a node in one step. On the right, the nodes sit in order of use, with the most recent nearest the head and the least recent nearest the tail. The head and tail boxes are fake nodes that never hold data. To use key 1, the map jumps straight to node 1, which is then unhooked and re-hooked just after head. To make room, we remove whatever sits just before tail.

Why the list must be doubly linked ​

To move a node to the front, you must first unhook it from where it is. To unhook a node, you need the node before it, so you can point that node past it.

In a singly linked list, finding the node before costs O(n), because you must walk from the head. If every node also has a prev pointer, the node before is one step away. That is the entire reason for the second pointer.

Why two dummy nodes ​

Adding at the front and removing at the back both have awkward cases: an empty list, a list of one, a node at the very edge. They all disappear if there are permanent fake nodes at both ends. Then every real node has a real neighbour on each side, and unhooking is always the same two lines with no ifs. This is the dummy-head idea from 4.9.2, used at both ends.

The solution ​

python
class Node:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val                 # (1)
        self.prev = self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}                                 # (2)
        self.head = Node()                            # (3)
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):                          # (4)
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):                       # (5)
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.map:                       # (6)
            return -1
        node = self.map[key]
        self._remove(node)                            # (7)
        self._add_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:                           # (8)
            self._remove(self.map[key])

        node = Node(key, value)                       # (9)
        self.map[key] = node
        self._add_front(node)

        if len(self.map) > self.cap:                  # (10)
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]                     # (11)
ts
class LNode {
  key = 0; val = 0;                                   // (1)
  prev: LNode | null = null;
  next: LNode | null = null;
  constructor(key = 0, val = 0) { this.key = key; this.val = val; }
}

class LRUCache {
  private cap: number;
  private map = new Map<number, LNode>();             // (2)
  private head = new LNode();                         // (3)
  private tail = new LNode();

  constructor(capacity: number) {
    this.cap = capacity;
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  private remove(node: LNode) {                       // (4)
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private addFront(node: LNode) {                     // (5)
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node;
  }

  get(key: number): number {
    const node = this.map.get(key);
    if (!node) return -1;                             // (6)
    this.remove(node);                                // (7)
    this.addFront(node);
    return node.val;
  }

  put(key: number, value: number): void {
    const existing = this.map.get(key);
    if (existing) this.remove(existing);              // (8)

    const node = new LNode(key, value);               // (9)
    this.map.set(key, node);
    this.addFront(node);

    if (this.map.size > this.cap) {                   // (10)
      const lru = this.tail.prev!;
      this.remove(lru);
      this.map.delete(lru.key);                       // (11)
    }
  }
}

Line by line ​

(1) Each node stores its key as well as its value. This looks like a waste, but line (11) needs it. Hold that thought.

(2) The map from key to node.

(3) The two dummy nodes, linked to each other. The list starts out as head ⇄ tail, with nothing real in between.

(4) Unhook a node. Point the node before it at the node after it, and the node after it back at the node before it. The node is now out of the chain. Thanks to the dummies, node.prev and node.next always exist, so there is no if.

(5) Hook a node in just after head. Four pointer changes, in this order:

  1. The new node's next is the current first real node (or tail if the list is empty).
  2. The new node's prev is head.
  3. The current first node points back at the new node.
  4. head points forward to the new node.

Order matters here. Steps 1 and 3 both read self.head.next, so step 4, which overwrites it, must come last.

(6) A key that is not there returns −1.

(7) Reading counts as using. Unhook the node and hook it back in at the front. If you forget this, you get a "least recently added" cache, which passes some tests and fails the ones that matter.

(8) Updating an existing key. Unhook its old node. A new node with the new value takes its place in the next line. (You could instead change the old node's value and move it to the front. That works just as well and creates one fewer object.)

(9) Create the node, record it in the map, and hook it in at the front.

(10) Too many keys? The least recently used node is always the one just before tail. Unhook it.

(11) Remove it from the map too, using its key. This is why line (1) stores the key. We found the node through the list, not the map. To delete its map entry, we need its key. Without the key stored on the node, we would have to search the whole map for it, which is O(n) and ruins the design. This is the detail most people miss.

Trace ​

Capacity 2. The list is shown front to back, without the dummies.

CallMap keys afterList after (most recent first)Returns
put(1, 1)1—
put(2, 2)2, 1—
get(1)1, 2 (1 moved to front)1
put(3, 3){1, 2, 3} → too many → remove 2 →3, 1—
get(2)3, 1−1
get(3)3, 13

At put(3, 3), the node just before tail was 2, so 2 was thrown out. Without the get(1) step, it would have been 1.

Complexity, derived ​

Time. Every operation is a few map operations, each O(1) on average, plus calls to _remove and _add_front, which change a fixed number of pointers with no loops. So get and put are both O(1).

Space. The map holds at most capacity entries, and the list holds at most capacity real nodes plus two dummies. So the space is O(\text{capacity}).

Edge cases ​

  • Capacity 1. Every new key throws out the previous one. The dummies make this work with no special case.
  • put on an existing key. It moves to the front with its new value, and nothing is thrown out, because the number of keys does not change.
  • get on a missing key. Returns −1 and changes nothing.
  • Many gets of the same key. It stays at the front.

The shortcut, and why to know both ​

Python has OrderedDict, a hash map that remembers the order keys were added and can move a key to either end in O(1).

python
from collections import OrderedDict

class LRUCache(OrderedDict):
    def __init__(self, capacity):
        self.cap = capacity

    def get(self, key):
        if key not in self:
            return -1
        self.move_to_end(key)              # mark as most recent
        return self[key]

    def put(self, key, value):
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.cap:
            self.popitem(last=False)       # remove the oldest key

JavaScript's Map also remembers insertion order. Deleting a key and setting it again moves it to the end, and map.keys().next().value gives the oldest key.

Both are correct, and both are how you would write it in real code. In an interview, write the manual version. The question is testing whether you can build the structure. OrderedDict is, inside, a hash map plus a doubly linked list doing exactly what you would have built. Say that, then offer the shortcut.

Variations you will meet ​

  • LFU Cache. Throw out the least frequently used key instead. You need a map from each use-count to a list of keys with that count, plus the current lowest count. It is much harder, and it is the natural follow-up. See 4.9.12.
  • Real caches. Database memory, your processor's cache and your browser's cache all face this choice. Many do not keep a true LRU order, because updating pointers on every single read is costly when many requests arrive at once. They use cheaper approximations instead.

The general lesson: when one structure cannot give you both fast lookup and a useful order, combine two and keep them in step.

What the interviewer will push on ​

"Why a doubly linked list?" Unhooking a node needs the node before it, and only a prev pointer gives that in O(1).

"Why does each node store its key?" To delete its map entry when it is thrown out.

"Does get change the order?" Yes. Reading is using.

"How would you make it safe for many threads?" The map and the list must always agree, so every operation must hold one lock around both changes. If another thread could see a node in the map that had already left the list, it would read broken data.

One thing to volunteer: state the design in one sentence before writing anything. "A hash map for O(1) lookup, a doubly linked list for O(1) reordering, and the map points at the list's nodes." Then build it.

Next: 4.9.10 Merge K Sorted Lists. The merge from 4.9.2, scaled up, and the first appearance of a heap.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet