Coding · Design a structure

LRU Cache

Reported in several places
Medium
SDE-1 and SDE
4 sources

Two or more independent public pages, at least one a candidate write-up.

The problem

Design a cache with a fixed capacity (at least 1) that supports get(key) and put(key, value), each in O(1) average time. get returns the stored value, or -1 when the key is absent, and either call counts as using that key; put updates an existing key or inserts a new one, and an insert into a full cache first evicts the key that was used longest ago. With capacity 2, put(1, 10), put(2, 20), get(1) returns 10, then put(3, 30) evicts key 2, so get(2) returns -1.

Restated in our own words, not a quote from Amazon or any page. The answer below is written for this site.

Try it first.The answer is covered until you pick. Talk it through against a 30 minute clock, or just read it.

Clarify first

Pin down the input before you touch the keyboard.

Before coding I would ask: can the capacity be 0, or is it at least 1? Are keys and values integers, and can a value be negative, given that -1 is the miss marker? Does put on an existing key count as a use? Does a get that misses change anything? Must it be thread safe? And may I use a language feature that remembers insertion order, or should I build the list by hand?

I would assume capacity of at least 1, integer keys, both put and get refresh recency, a miss changes nothing, a single thread, and O(1) average time per operation. I will build the list myself and mention the shortcut afterwards.

Brute force

Say the obvious answer and why it is too slow.

The simplest design keeps an array of [key, value] pairs ordered by use. get scans for the key, removes that pair and pushes it to the end; put does the same scan, and drops the first element when the array is full. It is correct and easy to reason about.

But every operation is O(capacity), because both the scan and the removal walk the array. With a capacity of 100,000 and a million operations that is on the order of 100 billion element moves, far beyond a time limit. Adding a Map for lookup fixes the search, but recency is still a problem: finding the oldest key means scanning for the smallest timestamp, which is again O(capacity).

The insight

The one idea that makes it fast, and why it is correct.

Brute force: O(capacity) per operation
Time: O(1) average per operation
Space: O(capacity)

Two structures cooperate, and each one covers the other's weakness. A hash map answers "where is this key" in O(1) on average. A doubly linked list keeps every entry in recency order. One sentinel node closes the list into a ring: the node after the sentinel is the most recently used, and the node before it is the one to evict.

The map stores the node itself, not just the value. That is the whole trick. Removing a node from the middle of a doubly linked list takes constant time only if you already hold the node, and the map hands it to you. So a get is: look up the node, unlink it, push it to the front, return its value. A put on a new key is: if the cache is full, take the node before the sentinel, unlink it and delete its key from the map, then create the new node and push it to the front.

The invariant is simple: the list order is the recency order, and the map holds exactly the keys that are in the list. Every operation changes a constant number of pointers and then the invariant holds again, so it is correct by construction. Two details cause most bugs. The node must store its own key, because eviction starts from a node and must delete that key from the map. And the sentinel removes all the null checks at the ends of the list.

Out loud I would say: "hash map plus doubly linked list, O(1) per operation." In JavaScript a Map also remembers insertion order, so deleting a key and setting it again moves it to the end; that is a valid shortcut, but it leans on engine behaviour, so I show the explicit list first.

Walk it through

A dry run on the example, step by step.

Capacity 2. Order lists keys from most to least recently used.

Operation	Result	Order after	Evicted
put(1, 10)	null	1	-
put(2, 20)	null	2, 1	-
get(1)	10	1, 2	-
put(3, 30)	null	3, 1	key 2
get(2)	-1	3, 1	-
put(4, 40)	null	4, 3	key 1
get(1)	-1	4, 3	-
get(3)	30	3, 4	-
get(4)	40	4, 3	-

Take capacity 2 and the operations in the table. The first two puts fill the cache, and the newest key always sits first in the order column. get(1) is a hit, so key 1 jumps to the front and key 2 becomes the oldest. put(3, 30) arrives at a full cache, so it evicts the oldest entry, key 2, and then puts 3 at the front.

The next get(2) is a miss and the order does not change, which is why a miss must not touch the list. put(4, 40) evicts key 1, because key 1 has gone unused longer than key 3. The last two gets are hits that reorder the list again. Watch the order column: at every row it is the single source of truth for who is evicted next.

The code

Runnable JavaScript, checked against test cases.

run.js

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.nodes = new Map();
    this.root = { key: 0, value: 0 };
    this.root.prev = this.root;
    this.root.next = this.root;
  }

  unlink(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  pushFront(node) {
    node.prev = this.root;
    node.next = this.root.next;
    this.root.next.prev = node;
    this.root.next = node;
  }

  get(key) {
    const node = this.nodes.get(key);
    if (node === undefined) return -1;
    this.unlink(node);
    this.pushFront(node);
    return node.value;
  }
  put(key, value) {
    const old = this.nodes.get(key);
    if (old !== undefined) this.unlink(old);
    else if (this.nodes.size === this.capacity) {
      const oldest = this.root.prev;
      this.unlink(oldest);
      this.nodes.delete(oldest.key);
    }
    const node = { key, value, prev: null, next: null };
    this.nodes.set(key, node);
    this.pushFront(node);
  }
}

function run(ops, args) {
  const cache = new LRUCache(args[0][0]);
  return ops.map((op, i) => (i === 0 ? null : (cache[op](...args[i]) ?? null)));
}

Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.

Try your own input

Write JavaScript that calls the code above and prints with console.log. It runs after the solution.

Edge cases

What to test before you say you are done.

Capacity 1: every new put evicts the only entry, and the code handles it because the oldest node and the newest node are the same node. Updating an existing key must not evict anything, even when the cache is full, so put checks the map before it checks the size. A put that overwrites a value also counts as a use, so it moves the node to the front.

A get on a missing key returns -1 and leaves the list alone. Re-inserting a key that was evicted earlier creates a fresh node, so there is no stale pointer. An empty cache has the sentinel pointing at itself, so a get on it simply misses. Values of 0 are fine, since the code tests for the node, not for a truthy value.

Follow-ups to expect

Where the interviewer pushes next.

How would you make this safe for many threads without one global lock?
How would you add a time-to-live to each entry?
What changes if eviction should be least frequently used instead of least recently used?
Can you build it with only a JavaScript Map, and what does that rely on?
How would you shard it across machines, and what happens to recency order?

Where candidates slip

The mistakes this problem punishes.

The most common slip is a singly linked list: removing a middle node then needs a scan for its predecessor, and the cache is O(n) again. The next is forgetting to store the key in the node, so eviction cannot delete the map entry and the cache slowly lies about its size.

Others: updating an existing key without refreshing its recency; evicting before checking whether the key already exists, which throws away an entry for nothing; using a falsy check such as if (!value), which treats a stored 0 as a miss; and getting pointer order wrong when linking, which is why I write the unlink and push-front helpers once and never inline them.

Have a go before you read.

Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.

Always show the answer straight away

Now make it stick

Solve it with tests Run a mock interview

Where this was reported

Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.

Now make it stick

Where this was reported

Learn the pattern first

More on design a structure