Skip to main content

79. LRU Cache

mediumAsked at Vercel

Design a Least-Recently-Used cache with O(1) get and put. Vercel asks this constantly — they literally maintain LRU caches at every edge POP and want to see if you can implement one with a doubly-linked list and a hash map.

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

Source citations

Public interview reports confirming this problem appears in Vercel loops.

  • Glassdoor (2025-Q4)— Vercel edge-runtime onsite; expected at every onsite.
  • Blind (2026-Q1)— Listed as the single most likely Vercel system-design-ish problem.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity) initializes the cache with positive size capacity; int get(int key) returns the value of the key if it exists, otherwise -1; void put(int key, int value) updates the value of the key or inserts the key-value pair. If the number of keys exceeds capacity, 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","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 tracking

Store (value, timestamp); on eviction, scan for the oldest.

Time
O(n) eviction
Space
O(n)
// O(n) eviction. Vercel rejects this.

Tradeoff: Eviction is O(n).

2. Doubly linked list + hash map (optimal)

Hash map: key -> DLL node. DLL ordered by recency. On access: move node to front. On eviction: remove tail. Dummy head/tail simplify edge cases.

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

Tradeoff: O(1) on every op. Dummy head/tail avoid the 'is this the only node' edge case. The DLL allows O(1) remove from any position.

Vercel-specific tips

Vercel grades the DLL + hash-map architecture. They may also accept JavaScript's built-in Map (which preserves insertion order), allowing a 10-line solution — mention this as the production-realistic answer. Bonus signal: noting the eviction edge case where the same key is updated (don't evict on existing-key update).

Common mistakes

  • Using only a Map without re-inserting on access — order doesn't reflect recency.
  • Evicting on update instead of insertion — wrong count after key collision.
  • Storing key only in map (not in node) — can't delete from map on eviction.

Follow-up questions

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

  • LFU Cache (LC 460, hard) — least-frequently-used.
  • TTL cache — time-based expiration.
  • Concurrent LRU — same shape with locking.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Map alone (insertion-order-preserving)?

JavaScript's Map iterates in insertion order. On get: delete and re-set to bump to the end. On put: same, with eviction = delete the first key. Production-realistic in 10 lines. Mention it but be ready to do the DLL version on demand.

Why DLL not singly-linked?

O(1) removal requires the predecessor pointer. Singly-linked needs O(n) to find it (unless paired with a per-node parent pointer).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →