MediumDesign a fixed-size cache that evicts the least-recently-used key — all in O(1).
Design a data structure for a Least Recently Used (LRU) cache supporting get(key) and put(key, value) in O(1) average time. get returns the value if present (and marks it as recently used) or -1. put inserts/updates a key (marking it recently used); if this exceeds the capacity, evict the least recently used key.
Walkthrough
try:
get(k) and put(k,v) must each run in O(1). Recency order = Map insertion order.
The Map keeps keys in insertion order: the first key is the least-recently-used (LRU), the last is the most-recently-used (MRU).
Intuition
Two needs: O(1) lookup by key, and O(1) knowledge of which key is the “oldest”. A hash map gives the first; an ordering that you can update cheaply gives the second.
Keep entries in recency order: least-recently-used at one end, most-recently-used at the other. Every access moves its entry to the MRU end.
On get, if the key exists, move it to the MRU end and return it. On put, insert/refresh at the MRU end.
When size exceeds capacity, the entry at the LRU end is exactly the one to evict. A JavaScript Map already preserves insertion order, so delete + re-set renews recency — or use an explicit hashmap + doubly linked list.
The algorithm
01get(key): miss → return -1. Hit → delete the key and re-insert it so it becomes the newest, then return its value.
02put(key,value): if the key exists, delete it first.
03Insert key at the most-recently-used end.
04If size now exceeds capacity, delete the least-recently-used entry (the oldest).
Reference implementations
1 · Ordered Map (concise)
Exploit insertion-ordered maps: delete + re-set renews a key as newest, and the first key is always the LRU to evict. This is the version animated above.
1
class LRUCache {
2
constructor(capacity) {
3
this.cap = capacity;
4
this.map = new Map(); // oldest → newest
5
}
6
get(key) {
7
if (!this.map.has(key)) return -1;
8
const v = this.map.get(key);
9
this.map.delete(key);
10
this.map.set(key, v); // renew as newest
11
return v;
12
}
13
put(key, value) {
14
if (this.map.has(key)) this.map.delete(key);
15
this.map.set(key, value);
16
if (this.map.size > this.cap) {
17
const lru = this.map.keys().next().value;
18
this.map.delete(lru); // evict oldest
19
}
20
}
21
}
2 · HashMap + Doubly Linked List (classic)
The textbook design: a hashmap from key to a node in a doubly linked list with head (MRU) and tail (LRU) sentinels. Unlink and re-link nodes in O(1). This is what the ordered-map trick does under the hood.
1
class Node {
2
constructor(key = 0, val = 0) {
3
this.key = key; this.val = val;
4
this.prev = null; this.next = null;
5
}
6
}
7
8
class LRUCache {
9
constructor(capacity) {
10
this.cap = capacity;
11
this.map = new Map(); // key -> Node
12
this.head = new Node(); // MRU side
13
this.tail = new Node(); // LRU side
14
this.head.next = this.tail;
15
this.tail.prev = this.head;
16
}
17
_remove(node) {
18
node.prev.next = node.next;
19
node.next.prev = node.prev;
20
}
21
_addFront(node) { // right after head = most recent
22
node.next = this.head.next;
23
node.prev = this.head;
24
this.head.next.prev = node;
25
this.head.next = node;
26
}
27
get(key) {
28
if (!this.map.has(key)) return -1;
29
const node = this.map.get(key);
30
this._remove(node);
31
this._addFront(node);
32
return node.val;
33
}
34
put(key, value) {
35
if (this.map.has(key)) this._remove(this.map.get(key));
36
const node = new Node(key, value);
37
this.map.set(key, node);
38
this._addFront(node);
39
if (this.map.size > this.cap) {
40
const lru = this.tail.prev; // node before tail = least recent