Skip to main content

84. LRU Cache

mediumAsked at Ola

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

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

Problem

Implement the LRUCache class with get(key) and put(key, value), both running in O(1). When capacity is exceeded, evict the least recently used key.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • At most 2*10^5 calls of get and put

Examples

Example 1

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

Approaches

1. Sorted list scan

Keep a list with timestamps; scan to find LRU on eviction.

Time
O(n) per op
Space
O(n)
// list with per-op scan; O(n) eviction

Tradeoff:

2. Map + doubly linked list

Map key->node; doubly linked list keeps recency. Move to front on access; pop tail on eviction.

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

Tradeoff:

Ola-specific tips

Ola interviewers love the Map insertion-order trick; tie it to keeping a recent-drivers cache hot in the dispatcher without external Redis.

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

Practice these live with InterviewChamp.AI →