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 Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-20

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.