Skip to main content

69. LRU Cache

mediumAsked at Reddit

Design an LRU cache with O(1) get and put. Reddit uses this to test data-structure composition (hash + doubly-linked-list) — the same primitive used in their hot-post cache eviction layer in front of Postgres.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit infra-team on-site favorite.
  • Blind (2025-12)— Reported as a Reddit must-know design question.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(capacity), get(key), put(key, value). 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","put","put","get","put","get","put","get","get","get"] [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
Output
[null,null,null,1,null,-1,null,-1,3,4]

Approaches

1. Map with timestamp

Map of key -> (value, lastUsed). Eviction scans for smallest timestamp.

Time
O(1) get, O(n) put
Space
O(n)
// Anti-pattern: put is O(n).

Tradeoff: Fails the O(1) put requirement.

2. Hash map + doubly linked list (optimal)

Map key -> node. DLL maintains order. Get: move to head. Put: insert at head, evict tail if over capacity. JS shortcut: use a Map (preserves insertion order).

Time
O(1) get and put
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.cap = 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);
    this.map.set(key, value);
    if (this.map.size > this.cap) {
      this.map.delete(this.map.keys().next().value);
    }
  }
}

Tradeoff: JS Map preserves insertion order — re-insertion is the 'move to head'. In other languages, implement DLL explicitly.

Reddit-specific tips

Reddit interviewers want you to articulate the design (hash + DLL) before showing language-specific shortcuts. Bonus signal: connect to their post-cache where hot posts stay in-memory and cold posts get evicted under memory pressure.

Common mistakes

  • Using only a Map without re-insertion (insertion order frozen at first insert).
  • Evicting the wrong end (head is most recent, tail/first-inserted is least).
  • Forgetting to remove from the map on eviction.

Follow-up questions

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

  • LFU Cache (LC 460).
  • Time-based key-value store (LC 981).
  • Concurrent LRU — thread-safe.

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 DLL instead of singly-linked?

Need O(1) removal of an arbitrary node (the one we just accessed). DLL gives prev/next pointers.

When to use the Map trick vs. DLL?

JS Map preserves insertion order, making it sufficient. For languages without ordered maps, build the DLL explicitly.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →