Skip to main content

1. LRU Cache

mediumAsked at Notion

Design an LRU cache supporting O(1) get and put. Notion asks this to test whether you can compose a hashmap with a doubly-linked list — the same pattern they use to cache hot blocks in the editor.

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

Source citations

Public interview reports confirming this problem appears in Notion loops.

  • Glassdoor (2026-Q1)— Notion phone screens recurringly use LRU as the data-structure design warm-up.
  • Blind (2025-11)— Notion frontend interviewers ask candidates to extend LRU with TTL.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with int capacity, int get(int key), and void put(int key, int value). Both operations must 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)
Output
1, -1

Explanation: Putting key 3 evicts key 2 because key 1 was recently used by get(1).

Example 2

Input
LRUCache(1); put(1,1); put(2,2); get(1)
Output
-1

Explanation: Capacity 1 means put(2) evicts key 1.

Approaches

1. Array + linear scan

Store entries in an array; on access, search linearly and move to front.

Time
O(n)
Space
O(n)
// Linear scan to find key, splice to front on access.
// Fails O(1) requirement.

Tradeoff: Trivially correct but violates the explicit O(1) contract.

2. Hashmap + doubly-linked list (optimal)

Hashmap gives O(1) lookup of nodes; the doubly-linked list gives O(1) move-to-front and tail-evict. Dummy head/tail sentinels avoid null checks.

Time
O(1)
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
    this.head = { prev: null, next: null };
    this.tail = { prev: this.head, next: null };
    this.head.next = this.tail;
  }
  _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, val) {
    if (this.map.has(key)) {
      const node = this.map.get(key); node.val = val;
      this._remove(node); this._addFront(node);
      return;
    }
    if (this.map.size === this.cap) {
      const lru = this.tail.prev;
      this._remove(lru); this.map.delete(lru.key);
    }
    const node = { key, val };
    this._addFront(node); this.map.set(key, node);
  }
}

Tradeoff: True O(1). The dummy head/tail trick eliminates ~6 edge cases. JavaScript Map preserves insertion order — a Map-only solution also works.

Notion-specific tips

Notion grades LRU on whether you immediately reach for a hashmap + linked list and explain the two invariants: 'hashmap maps key to node' and 'list orders nodes by recency.' Bonus signal: mention that Notion's block-cache layer uses similar eviction for hot pages, and discuss extending to TTL or write-behind for the editor's autosave path.

Common mistakes

  • Using a singly-linked list — you cannot remove a known node in O(1) without the prev pointer.
  • Forgetting to update the linked list on get — that defeats 'recently used' semantics.
  • Off-by-one on capacity check (evict AFTER insert, not before).

Follow-up questions

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

  • Add a TTL: evict not just LRU but also expired entries.
  • Make it thread-safe — what locks would you use?
  • Design LFU (LC 460) — what changes versus LRU?

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 a doubly-linked list and not just a Map?

JavaScript's Map preserves insertion order, so you can re-insert keys to bump recency. But in languages without that guarantee, you need the explicit DLL. Both are O(1).

Why dummy head/tail nodes?

They eliminate boundary conditions when adding/removing the first or last element. Without them you'd write 4+ null checks per operation.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →