LRU Cache

The problem. Design a Least Recently Used (LRU) cache with a fixed capacity. get(key) returns the value if the key is cached, otherwise -1. put(key, value) adds or updates a key; if that makes the cache hold more than capacity keys, it evicts the key used least recently. Both operations must run in O(1) average time. Using a key — get or put — makes it the most recently used.

Example

LRUCache(2)
put(1, 1), put(2, 2)
get(1)      -> 1      (1 is now the most recent)
put(3, 3)             (full: evicts 2, the least recent)
get(2)      -> -1
put(4, 4)             (evicts 1)
get(1)      -> -1
get(3)      -> 3
get(4)      -> 4

The idea: a hash map for finding, a doubly linked list for ordering

The cache needs two things at once. It must find a key's entry in O(1) — that's a hash map. And it must keep entries in order of use, so that it can move any entry to the front and remove the oldest from the back, also in O(1) — that's a doubly linked list. An array can't move an item from the middle to the front without shifting; a singly linked list can't unlink a node without first finding the node before it. A doubly linked node knows both neighbours, so moving or removing it is a few pointer changes.

The map stores key → node, so get jumps straight to the node, unlinks it and re-adds it at the front. Two sentinel nodes, head and tail, sit at the ends permanently: the list is never truly empty, so unlinking and adding never need a null check. The least recently used entry is always tail.prev.

1. Brute force: an array of keys in order of use

1class LRUCache {2  constructor(capacity) {3    this.capacity = capacity;4    this.values = new Map();           // key -> value5    this.order = [];                   // keys, least recently used first6  }7  touch(key) {                         // move key to the most recent end: O(n)8    const i = this.order.indexOf(key);9    if (i >= 0) this.order.splice(i, 1);10    this.order.push(key);11  }12  get(key) {13    if (!this.values.has(key)) return -1;14    this.touch(key);15    return this.values.get(key);16  }17  put(key, value) {18    this.values.set(key, value);19    this.touch(key);20    if (this.order.length > this.capacity) {21      const lru = this.order.shift();  // the front of the array is the least recent22      this.values.delete(lru);23    }24  }25}

Time O(capacity) per operation, space O(capacity). Finding the key in the order array and shifting the array after removing it are both linear. Correct, but not the O(1) the question asks for.

2. Hash map + doubly linked list

1class Entry {2  constructor(key, value) {3    this.key = key;4    this.value = value;5    this.prev = null;6    this.next = null;7  }8}9 10class LRUCache {11  constructor(capacity) {12    this.capacity = capacity;13    this.map = new Map();              // key -> its node, so any entry is found in O(1)14    this.head = new Entry(0, 0);       // sentinels: head.next is the most recently used,15    this.tail = new Entry(0, 0);       // tail.prev the least recently used16    this.head.next = this.tail;17    this.tail.prev = this.head;18  }19  remove(node) {                       // unlink a node in O(1)20    node.prev.next = node.next;21    node.next.prev = node.prev;22  }23  addFront(node) {                     // insert right after the head sentinel24    node.prev = this.head;25    node.next = this.head.next;26    this.head.next.prev = node;27    this.head.next = node;28  }29  get(key) {30    const node = this.map.get(key);31    if (node === undefined) return -1;32    this.remove(node);                 // it was just used: move it to the front33    this.addFront(node);34    return node.value;35  }36  put(key, value) {37    if (this.map.has(key)) this.remove(this.map.get(key));38    const node = new Entry(key, value);39    this.map.set(key, node);40    this.addFront(node);41    if (this.map.size > this.capacity) {42      const lru = this.tail.prev;      // the least recently used is at the back43      this.remove(lru);44      this.map.delete(lru.key);45    }46  }47}

Time O(1) per operation, space O(capacity). Each operation is a hash lookup plus a constant number of pointer changes. The node stores its key as well as its value so that, when it's evicted from the back of the list, the map entry can be deleted too.

Most languages ship this combination: JavaScript's Map remembers insertion order (delete and re-set a key to refresh it), Python has collections.OrderedDict with move_to_end, and Java's LinkedHashMap takes an access-order flag and a removeEldestEntry hook. Each is a hash map threaded through a doubly linked list — the interview wants you to build it yourself.

Comparing the approaches

LRU Cache is one of the most asked design questions of all, because it combines two data structures so that each covers the other's weakness.

Edge cases to test

Variations