Skip to main content

77. LRU Cache

mediumAsked at Snowflake

Design an LRU cache with O(1) get and put. Snowflake asks this constantly because it's the foundation of their warehouse cache — frequently-accessed micro-partitions stay hot in SSD; cold ones get evicted by exactly this policy.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake storage-team uses this as canonical cache-design question.
  • Blind (2025-12)— Recurring at Snowflake SDE-II onsites.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity) initialize with positive size capacity. int get(int key) return the value of the key if it exists, otherwise return -1. void put(int key, int value) update the value of the key if exists. Otherwise, add the key-value pair. If the number of keys exceeds capacity, evict the least recently used key. Both 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), put(4,4), get(1), get(3), get(4)
Output
1, -1, -1, 3, 4

Approaches

1. Array with timestamps

Use array of (key, value, timestamp). On get/put, scan to update timestamps and find LRU.

Time
O(n) per op
Space
O(n)
// outline only — too slow.

Tradeoff: Linear ops. Violates the O(1) requirement.

2. Hash map + doubly linked list (optimal)

Hash map: key -> node. DLL: head (most recent) to tail (least recent). On get: move to head. On put: insert at head, evict from tail when over capacity.

Time
O(1) amortized per op
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
    this.head = { key: -1, val: -1, prev: null, next: null };
    this.tail = { key: -1, val: -1, prev: null, next: null };
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  _insertFront(node) {
    node.prev = this.head;
    node.next = this.head.next;
    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._insertFront(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._insertFront(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: value, prev: null, next: null };
    this._insertFront(node);
    this.map.set(key, node);
  }
}

Tradeoff: True O(1) per op via the DLL pointer manipulation + hash map lookup.

Snowflake-specific tips

Snowflake interviewers grade this on whether you can write the DLL operations cleanly. Bonus signal: connect to warehouse SSD cache eviction — Snowflake's compute nodes cache hot micro-partitions on local SSD; the eviction policy is LRU (or a variant), and the bookkeeping for promote/demote is exactly this structure scaled up.

Common mistakes

  • Using just Map without ordering — Map iteration order in JS is insertion order, which helps but inserting-then-deleting isn't O(1) the same way.
  • Forgetting sentinel head and tail nodes — leads to special cases for boundary inserts.
  • Not removing from the map when evicting from the DLL — map grows unbounded.

Follow-up questions

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

  • LFU Cache (LC 460).
  • Thread-safe LRU.
  • How does Snowflake's local SSD cache evict micro-partitions?

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 not singly-linked?

Removing a node from a DLL is O(1) given a reference. A singly-linked list requires walking to find prev, making removal O(n).

Can you use the Map's insertion-order?

JS Map preserves insertion order. delete + set is technically O(1) and equivalent to moving-to-end. It's accepted but the DLL version makes the data structure choice explicit.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →