Skip to main content

12. LRU Cache

mediumAsked at Byju's

Design an O(1) get/put cache that evicts the least-recently-used key when full.

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) and put(key, value) so that both operations run in O(1) time. When the cache reaches its capacity, evict the least recently used key before inserting a new one.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key, value <= 10^5
  • At most 2 * 10^5 calls

Examples

Example 1

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

Example 2

Input
capacity=2; put(2,1), put(1,1), put(2,3), get(2)
Output
3

Approaches

1. Array scan

Store entries in an array, scan linearly to find or evict.

Time
O(n)
Space
O(n)
class LRU{ constructor(c){this.c=c;this.a=[];}
  get(k){const i=this.a.findIndex(e=>e[0]===k); if(i<0) return -1; const e=this.a.splice(i,1)[0]; this.a.push(e); return e[1]; }
  put(k,v){const i=this.a.findIndex(e=>e[0]===k); if(i>=0) this.a.splice(i,1); else if(this.a.length>=this.c) this.a.shift(); this.a.push([k,v]); }
}

Tradeoff:

2. Map ordered iteration

JavaScript Map preserves insertion order; on access, delete and re-set to bump the key to the tail. Evict via the first key in the iterator.

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

Tradeoff:

Byju's-specific tips

Byju's video-tutoring backend uses LRU-style caches for cached lesson playbacks, so call out that connection during the design walk-through.

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

Practice these live with InterviewChamp.AI →