Skip to main content

146. LRU Cache

mediumAsked at Robinhood

Design an LRU cache that supports get and put in O(1). Robinhood asks this because hot-path market-data services rely on bounded eviction caches — the right answer is a doubly-linked list plus a hash map, not just one of the two.

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

Source citations

Public interview reports confirming this problem appears in Robinhood loops.

  • Glassdoor (2026-Q1)— Robinhood SWE-II and senior-IC onsite reports repeatedly cite LRU Cache as the design-coding hybrid round.
  • Blind (2025-11)— Robinhood backend SWE-II trip report names LRU Cache as the 45-minute coding round.
  • Levels.fyi (2025-09)— Robinhood SWE-II interview blueprint includes LRU as a recurring problem.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement LRUCache(int capacity), int get(int key), and void put(int key, int value). Both operations must run in O(1) average time. When the cache exceeds capacity, evict the least recently used key.

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

Explanation: put(3,3) evicts key 2 (the LRU after get(1) refreshed 1). put(4,4) evicts key 1.

Approaches

1. Array + last-used scan

Store {key, value, lastUsedTs} in an array. On get/put scan for the entry; on eviction scan for the min timestamp.

Time
O(n) per op
Space
O(n)
class LRUCacheSlow {
  constructor(capacity) {
    this.cap = capacity;
    this.data = []; // {key, value, ts}
    this.tick = 0;
  }
  get(key) {
    const e = this.data.find(x => x.key === key);
    if (!e) return -1;
    e.ts = ++this.tick;
    return e.value;
  }
  put(key, value) {
    const e = this.data.find(x => x.key === key);
    if (e) {
      e.value = value;
      e.ts = ++this.tick;
      return;
    }
    if (this.data.length === this.cap) {
      let minIdx = 0;
      for (let i = 1; i < this.data.length; i++) {
        if (this.data[i].ts < this.data[minIdx].ts) minIdx = i;
      }
      this.data.splice(minIdx, 1);
    }
    this.data.push({ key, value, ts: ++this.tick });
  }
}

Tradeoff: Trivial to write but O(n) per op. Worth naming explicitly so the interviewer hears you considered it and chose against it.

2. Hash map + doubly-linked list (optimal)

Map key -> node. Doubly-linked list ordered MRU-at-head, LRU-at-tail. Get/put move node to head; eviction removes tail.

Time
O(1) per op
Space
O(capacity)
class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
    this.head = new Node(0, 0); // dummy
    this.tail = new Node(0, 0); // dummy
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  _addToFront(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._addToFront(node);
    return node.value;
  }
  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.value = value;
      this._remove(node);
      this._addToFront(node);
      return;
    }
    if (this.map.size === this.cap) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
    const node = new Node(key, value);
    this._addToFront(node);
    this.map.set(key, node);
  }
}

Tradeoff: O(1) per op at the cost of pointer bookkeeping. Dummy head and tail eliminate edge cases (no null checks on prev/next). This is the answer Robinhood expects.

3. JavaScript Map insertion-order (idiomatic optimal)

JS Map preserves insertion order. Use delete + set to move-to-end on touch; iterator.next().value to find LRU.

Time
O(1) per op
Space
O(capacity)
class LRUCacheMap {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const v = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, v);
    return v;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size === this.cap) {
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest);
    }
    this.map.set(key, value);
  }
}

Tradeoff: Cleanest possible code in JS — leverages Map's insertion-order property. Many Robinhood interviewers accept this; some will still ask you to write the doubly-linked-list version to demonstrate you understand the underlying structure.

Robinhood-specific tips

Robinhood interviewers will let you start with the Map insertion-order trick if you state up front that you know it relies on JS Map's defined insertion-order behavior. Most still ask you to follow up with the explicit doubly-linked-list version — they want to see that you can implement the underlying structure, not just use the language feature. Use dummy head/tail nodes; it eliminates entire classes of off-by-one bugs.

Common mistakes

  • Forgetting to remove the key from the hash map when evicting from the list — leads to stale references.
  • Updating value on put without moving the node to the front (most-recently-used).
  • Forgetting dummy head/tail nodes and crashing on the first insert/remove because prev/next is null.

Follow-up questions

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

  • LFU Cache (LeetCode 460) — Least Frequently Used; two-level structure.
  • TTL Cache — entries expire after T ms; combine LRU with a sorted timestamp structure.
  • Distributed LRU — sketch how you'd shard the cache across servers.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Doubly-linked list vs JS Map — which does Robinhood prefer?

Both are accepted, but you should be able to write the explicit doubly-linked-list version if asked. The Map version proves language fluency; the list version proves you understand the underlying data structure. Strong candidates show both.

Why a doubly-linked list and not a singly-linked one?

On get/put you need to remove a node from the middle in O(1). Without a back-pointer (prev), removing requires scanning from head to find the predecessor — that's O(n).

Why dummy head and tail nodes?

They eliminate null checks. Without them, removing the first or last real node means you have to special-case 'is head null after this?' on every operation. Dummies make the prev/next pointers always non-null.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →