Skip to main content

146. LRU Cache

mediumAsked at DoorDash

Design a cache that evicts the least recently used key when full. DoorDash asks this for backend SWE loops because logistics systems lean on LRU eviction for hot order/driver lookups — they want both get and put in O(1).

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

Source citations

Public interview reports confirming this problem appears in DoorDash loops.

  • Glassdoor (2026-Q1)— DoorDash SWE onsite reports list LRU Cache as a near-default data-structure design question.
  • Blind (2025-11)— DoorDash new-grad + SDE2 reports cite this as a backend-team favorite.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity) initialize the LRU cache with positive size capacity. int get(int key) return the value of the key if the key exists, otherwise return -1. void put(int key, int value) update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. The functions get and put must each run in O(1) average time complexity.

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

Approaches

1. Hash map + JS Map (insertion-ordered)

JS Map preserves insertion order. Delete + re-insert on access to refresh recency.

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

Tradeoff: Concise and uses language feature. Often accepted at DoorDash, but expect a follow-up: 'now do it without language built-ins.'

2. Doubly linked list + hash map (canonical)

Hash map key -> DLL node + doubly linked list with sentinel head/tail. Move-to-front on get/put; evict from tail.

Time
O(1) worst case
Space
O(capacity)
class Node {
  constructor(key, val) { this.key = key; this.val = val; this.prev = null; this.next = null; }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = new Node(0, 0);
    this.tail = new Node(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  _remove(node) { node.prev.next = node.next; node.next.prev = node.prev; }
  _addFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node);
    this._addFront(node);
    return node.val;
  }
  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.val = value;
      this._remove(node);
      this._addFront(node);
      return;
    }
    if (this.map.size >= this.capacity) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
    const node = new Node(key, value);
    this.map.set(key, node);
    this._addFront(node);
  }
}

Tradeoff: The textbook answer. Sentinel nodes eliminate edge cases. DoorDash interviewers may insist on this — backend rounds care about understanding the actual data structures.

DoorDash-specific tips

DoorDash interviewers grade on two axes: (1) you can articulate WHY both structures are needed (hash for lookup, DLL for O(1) reorder); (2) sentinel head/tail. Some interviewers say 'don't use language built-ins' — in that case the DLL version is required.

Common mistakes

  • Using a singly linked list — O(1) node removal requires the prev pointer.
  • Forgetting to remove the evicted key from the hash map (memory leak).
  • Off-by-one on capacity check.
  • Forgetting sentinels — leads to null derefs at head or tail.

Follow-up questions

An interviewer at DoorDash may pivot to one of these next:

  • LFU Cache (LC 460) — least frequently used.
  • Add TTL per key.
  • Make it thread-safe (locking or sharded).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why both data structures?

Hash map gives O(1) lookup. DLL gives O(1) splice (move to front, remove from tail). Neither alone gives both.

Will DoorDash accept the JS Map shortcut?

Sometimes, for conciseness. Be ready to switch to the DLL version if asked — backend interviewers usually push for it.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill LRU Cache and other DoorDash interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →