Skip to main content

15. LRU Cache

mediumAsked at Chime

Design a Least Recently Used cache with O(1) get and put operations.

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

Problem

Design a data structure that supports get(key) returning the value if the key exists or -1 otherwise, and put(key, value) inserting or updating the value. When the cache reaches its capacity, evict the least recently used key. Both operations must run in O(1) average time.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • At most 2 * 10^5 calls will be made 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
capacity=1; put(2,1); get(2); put(3,2); get(2); get(3)
Output
[null,null,1,null,-1,2]

Approaches

1. Array of pairs

Store entries in an array and scan on every get; reorder on access.

Time
O(n)
Space
O(n)
// get: linear scan, splice to front
// put: linear scan; if full, pop tail; unshift new

Tradeoff:

2. Hash map + doubly linked list

Use a hash map of key to list-node for O(1) lookup and a doubly linked list ordered by recency. Move-to-front on access, evict tail on overflow.

Time
O(1)
Space
O(capacity)
class LRUCache {
  constructor(cap) {
    this.cap = cap;
    this.map = new Map();
  }
  get(k) {
    if (!this.map.has(k)) return -1;
    const v = this.map.get(k);
    this.map.delete(k);
    this.map.set(k, v);
    return v;
  }
  put(k, v) {
    if (this.map.has(k)) this.map.delete(k);
    else if (this.map.size >= this.cap) {
      this.map.delete(this.map.keys().next().value);
    }
    this.map.set(k, v);
  }
}

Tradeoff:

Chime-specific tips

Chime runs LRU layers in front of their balance-projection service, so interviewers reward candidates who can explain eviction semantics under cache stampede.

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

Practice these live with InterviewChamp.AI →