Skip to main content

23. LRU Cache

mediumAsked at Ramp

Design a data structure with O(1) get and put plus least-recently-used eviction.

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 the LRUCache class with get(key) and put(key, value), both running in average O(1) time. When capacity is exceeded, evict the least recently used key.

Constraints

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

Examples

Example 1

Input
LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2)
Output
1, then -1

Example 2

Input
LRUCache(1); put(1,1); put(2,2); get(1)
Output
-1

Approaches

1. Array-backed brute force

Use an array of [key, value]; on every get/put scan for the key.

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

Tradeoff:

2. Map preserves insertion order

JavaScript Map keeps insertion order; delete-then-set moves a key to the most-recent position; eviction pops the first key.

Time
O(1)
Space
O(capacity)
class LRUCache {
  constructor(capacity) { this.cap = capacity; this.map = new Map(); }
  get(key) {
    if (!this.map.has(key)) return -1;
    const v = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, v);
    return v;
  }
  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:

Ramp-specific tips

Ramp's corporate card rules engine caches per-policy decisions with an LRU layer in front of the rule store — explaining the insertion-order trick (or the equivalent map + doubly-linked-list) is the bonus signal.

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

Practice these live with InterviewChamp.AI →