Skip to main content

17. LRU Cache

mediumAsked at Monzo

Design a fixed-capacity cache for hot account-balance lookups that evicts the least recently used entry.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement get(key) which returns the value or -1, and put(key, value) which inserts or updates and evicts the LRU entry when capacity is exceeded. Both operations must run in average O(1).

Constraints

  • 1 <= capacity <= 3000
  • Up to 10^5 calls to get and put

Examples

Example 1

Input
LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2)
Output
[1, -1]

Example 2

Input
put(4,4); get(1); get(3); get(4)
Output
[-1, 3, 4]

Approaches

1. Insertion-ordered map

Use JavaScript Map iteration order: delete and re-insert on access; pop the first key on overflow.

Time
O(1) amortized
Space
O(capacity)
class LRU {
  constructor(c) { this.c = c; this.m = new Map(); }
  get(k) { if (!this.m.has(k)) return -1; const v = this.m.get(k); this.m.delete(k); this.m.set(k, v); return v; }
  put(k, v) { if (this.m.has(k)) this.m.delete(k); this.m.set(k, v); if (this.m.size > this.c) this.m.delete(this.m.keys().next().value); }
}

Tradeoff:

2. Hash map + doubly linked list

Hash key to node; doubly linked list orders nodes by recency. Move-to-head on access; evict from tail on overflow.

Time
O(1)
Space
O(capacity)
class Node { constructor(k, v) { this.k=k; this.v=v; this.prev=this.next=null; } }
class LRUCache {
  constructor(c) { this.c=c; this.m=new Map(); this.h=new Node(); this.t=new Node(); this.h.next=this.t; this.t.prev=this.h; }
  _rm(n) { n.prev.next=n.next; n.next.prev=n.prev; }
  _add(n) { n.next=this.h.next; n.prev=this.h; this.h.next.prev=n; this.h.next=n; }
  get(k) { if (!this.m.has(k)) return -1; const n=this.m.get(k); this._rm(n); this._add(n); return n.v; }
  put(k, v) { if (this.m.has(k)) { const n=this.m.get(k); n.v=v; this._rm(n); this._add(n); return; } const n=new Node(k,v); this.m.set(k,n); this._add(n); if (this.m.size>this.c) { const e=this.t.prev; this._rm(e); this.m.delete(e.k); } }
}

Tradeoff:

Monzo-specific tips

Monzo expects you to defend O(1) on every op because their hot-balance path is on the faster-payments critical chain.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill LRU Cache and other Monzo interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →