Skip to main content

18. LRU Cache

mediumAsked at ByteDance

Design an LRU cache with O(1) get and put — ByteDance asks this nearly every loop because it mirrors how their video-thumbnail edge cache must evict cold tiles in microseconds.

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

Problem

Design a Least Recently Used (LRU) cache with a fixed capacity. Implement get(key) and put(key, value), both running in O(1) average time. When the cache exceeds capacity on put, evict the least recently used key.

Constraints

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

Examples

Example 1

Input
ops = [put(1,1), put(2,2), get(1), put(3,3), get(2)]
Output
[null, null, 1, null, -1]

Example 2

Input
ops = [put(1,1), get(1), put(2,2), get(1)]
Output
[null, 1, null, 1]

Approaches

1. Array + linear scan

Store entries in an array; on get, move the entry to the front; on overflow, drop the tail.

Time
O(n) per op
Space
O(capacity)
// array-based store with linear search and splice on touch

Tradeoff:

2. Hash map plus doubly linked list (or Map insertion order)

Use a Map whose insertion order is the recency order. Re-insert on hit; pop the oldest on overflow.

Time
O(1) avg per op
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.capacity = 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.capacity) {
      this.map.delete(this.map.keys().next().value);
    }
  }
}

Tradeoff:

ByteDance-specific tips

ByteDance interviewers want you to call out the hash-map plus linked-list pairing as a hot pattern for their edge caches before showing any code, then justify the JavaScript Map shortcut on top.

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

Practice these live with InterviewChamp.AI →