Skip to main content

18. LRU Cache

mediumAsked at GitLab

Implement a cache with O(1) get and put that evicts the least recently used entry when full.

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

Problem

Design an LRU cache with capacity C supporting get(key) and put(key, value) in O(1). On overflow, evict the least recently accessed key.

Constraints

  • 1 <= capacity <= 3000
  • Up to 2*10^5 operations
  • 0 <= key, value <= 10^4

Examples

Example 1

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

Example 2

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

Approaches

1. Array of pairs

Linear scan for get/put; splice the array on access to mark recency.

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

Tradeoff:

2. Map insertion order

JavaScript Map preserves insertion order. Delete-then-set on access bumps a key to most-recently-used; the first key from keys() is the LRU victim.

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

Tradeoff:

GitLab-specific tips

GitLab uses LRU as a proxy for how you would cap their merge-request review caches per runner — they will probe whether you understand recency vs frequency trade-offs in long-lived pipelines.

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

Practice these live with InterviewChamp.AI →