Skip to main content

14. LRU Cache

mediumAsked at Mercury

Design a cache with O(1) get and put that evicts the least recently used entry on overflow.

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

Problem

Implement an LRU cache supporting get(key) and put(key, value) in O(1). When capacity is exceeded, evict the least recently used entry. Both reading and writing count as access for recency.

Constraints

  • 1 <= capacity <= 3000
  • Up to 2*10^5 calls
  • Keys and values fit in int32

Examples

Example 1

Input
cap=2; put(1,1); put(2,2); get(1); put(3,3); get(2)
Output
1 then -1 (2 evicted)

Example 2

Input
cap=1; put(1,1); put(2,2); get(1)
Output
-1

Approaches

1. Sorted access list

Track usage by re-sorting an access array on each touch.

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

Tradeoff:

2. Map with insertion-order rotation

JavaScript Map preserves insertion order, so deleting and re-inserting on access naturally puts the freshest entry last and exposes the LRU at iterator head.

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

Tradeoff:

Mercury-specific tips

Mercury frames LRU as their balance-cache layer — each cache hit/miss controls whether a transaction page reads the materialized account totals or hits the multi-account aggregation service.

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

Practice these live with InterviewChamp.AI →