Skip to main content

18. LRU Cache

mediumAsked at Squarespace

Design a least-recently-used cache with O(1) get and put; Squarespace uses it to probe whether you combine a hash map with a doubly linked list correctly.

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

Problem

Implement a class LRUCache(capacity) supporting get(key) and put(key, value). Both should run in average O(1) time. When at capacity, put evicts the least recently used key.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key, value <= 10^4
  • At most 2 * 10^5 calls of get and put

Examples

Example 1

Input
new LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2)
Output
1, then -1

Example 2

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

Approaches

1. Map with rebuild on get

Use a Map and delete-then-set on each access so iteration order matches recency.

Time
O(1) amortized
Space
O(capacity)
class LRUCache { 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); else if(this.m.size>=this.c) this.m.delete(this.m.keys().next().value); this.m.set(k,v); } }

Tradeoff:

2. Hash map + doubly linked list

Hash gives O(1) key lookup; doubly linked list lets you move a node to the front and evict the tail in O(1).

Time
O(1)
Space
O(capacity)
class LRUCache {
  constructor(c) { this.c = c; this.m = new Map(); this.h = {}; this.t = {}; this.h.n = this.t; this.t.p = this.h; }
  _add(n) { n.n = this.h.n; n.p = this.h; this.h.n.p = n; this.h.n = n; }
  _rm(n) { n.p.n = n.n; n.n.p = n.p; }
  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)) this._rm(this.m.get(k));
    const n = { k, v }; this._add(n); this.m.set(k, n);
    if (this.m.size > this.c) { const lru = this.t.p; this._rm(lru); this.m.delete(lru.k); }
  }
}

Tradeoff:

Squarespace-specific tips

Squarespace evaluators love when you connect the LRU pattern to their template-render cache, which evicts least recently published site versions to keep edge memory bounded.

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 Squarespace interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →