Skip to main content

23. LRU Cache

mediumAsked at Wise

Design a get/put cache with O(1) eviction of the least recently used key — Wise probes this for FX rate caches in front of their pricing oracles.

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

Problem

Design a data structure that supports get(key) and put(key, value) in O(1) time, evicting the least recently used key when capacity is exceeded.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key, value <= 10^4
  • get and put must be O(1) average

Examples

Example 1

Input
ops=['LRUCache',2,'put',1,1,'put',2,2,'get',1,'put',3,3,'get',2]
Output
[null,null,null,1,null,-1]

Example 2

Input
ops=['LRUCache',1,'put',1,1,'put',2,2,'get',1]
Output
[null,null,null,-1]

Approaches

1. Array shuffle on use

Use an array of [k,v]; on get/put move the entry to the front and pop the tail when over capacity.

Time
O(n) per op
Space
O(n)
class LRUCache{
  constructor(cap){ this.cap=cap; this.list=[]; }
  get(k){ const i=this.list.findIndex(p=>p[0]===k); if(i<0) return -1; const e=this.list.splice(i,1)[0]; this.list.unshift(e); return e[1]; }
  put(k,v){ const i=this.list.findIndex(p=>p[0]===k); if(i>=0) this.list.splice(i,1); this.list.unshift([k,v]); if (this.list.length>this.cap) this.list.pop(); }
}

Tradeoff:

2. Hash map plus doubly linked list

JS Map preserves insertion order, so delete-then-set promotes to most-recent; iterating keys().next().value gives the oldest in O(1).

Time
O(1) per op
Space
O(n)
class LRUCache{
  constructor(capacity){ this.cap = capacity; this.map = new Map(); }
  get(key){
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, val);
    return val;
  }
  put(key, value){
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.cap){
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest);
    }
  }
}

Tradeoff:

Wise-specific tips

Wise grades whether you can hit true O(1) — their FX-rate cache sits on the hot path and any O(n) eviction would blow their tail latency budget.

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

Practice these live with InterviewChamp.AI →