Skip to main content

23. LRU Cache

mediumAsked at MercadoLibre

Design a least-recently-used cache supporting O(1) get and put.

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

Problem

Design a data structure that supports get(key) and put(key, value) in O(1) average time. The cache has a fixed capacity; when it would exceed capacity on a new put, evict the least-recently-used key.

Constraints

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

Examples

Example 1

Input
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
LRUCache(1); put(2,1); get(2); put(3,2); get(2)
Output
[null,null,1,null,-1]

Approaches

1. Array of pairs

Store [key,value] pairs in an array; promote on get by removing and reinserting at the tail.

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

Tradeoff:

2. Map insertion order (JS Map)

JavaScript Map preserves insertion order; delete-and-set on access bumps the entry to most-recently-used, and the first key is least-recently-used.

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

Tradeoff:

MercadoLibre-specific tips

MercadoLibre platform engineers ask this because Mercado Pago's session cache evicts the same way — show you understand both the textbook doubly-linked-list+map version and the production shortcut JavaScript's Map gives you.

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

Practice these live with InterviewChamp.AI →