146. LRU Cache

mediumAsked at Shopify

LRU Cache is Shopify's canonical 'design a data structure' round. Storefronts have heavy cache eviction needs (product pages, theme assets, session tokens), so the interviewer is grading whether you reach for the doubly-linked-list + hash-map combo and explain why neither alone gives O(1) get + put.

By Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-19

Source citations

Public interview reports confirming this problem appears in Shopify loops.

Glassdoor (2026-Q1)— Shopify Senior Backend Developer + Engineering Lead onsites repeatedly include LRU Cache as the data-structure-design round.
Blind (2025-12)— Shopify Senior+ Backend offers report LRU as the standard data-structure round, often with a TTL follow-up.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement get(key) and put(key, value), both 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

[null,null,null,1,null,-1,null,-1,3,4]

Explanation: After put(3,3) the cache is full so key 2 (least recently used) is evicted.

Approaches

1. Hash map with insertion-ordered Map

JavaScript Map preserves insertion order. Delete + re-insert on get to refresh recency; iterate Map.keys() to find LRU on eviction.

Time: O(1) get, O(1) put amortized
Space: O(capacity)

class LRUCacheMap {
  constructor(capacity) {
    this.capacity = 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);
    else if (this.map.size >= this.capacity) {
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest);
    }
    this.map.set(key, value);
  }
}

Tradeoff: Ships in 15 lines. Same O(1) amortized complexity as the doubly-linked-list version, just leaning on a language feature. Most Shopify interviewers accept this if you also mention the underlying data structure.

2. Doubly linked list + hash map (canonical)

Hash map from key to node pointer + doubly linked list with sentinel head/tail. Move-to-front on every get/put.

Time: O(1) get, O(1) put worst case
Space: O(capacity)

class Node {
  constructor(key, val) { this.key = key; this.val = val; this.prev = null; this.next = null; }
}

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

Tradeoff: The textbook answer. Sentinel head/tail nodes eliminate the null-pointer checks that break candidates under time pressure. Worst-case O(1) per operation (the Map version is amortized only because Map's iteration can be implementation-dependent).

Shopify-specific tips

Shopify's expected follow-ups: (1) add TTL per key, (2) make it thread-safe (talk about a mutex around mutations, or sharded caches), (3) what if the workload is read-heavy and write-rare (mention W-TinyLFU or 2Q). Senior candidates are also asked to wire this behind an HTTP cache layer — be ready to discuss cache invalidation triggers (publish events, webhook callbacks).

Common mistakes

Using a singly linked list — you need O(1) node removal, which requires prev pointers.
Forgetting to delete the evicted key from the hash map (causes a memory leak that only surfaces under load).
Off-by-one on capacity: evict when size >= capacity BEFORE inserting, not after.
Forgetting that put on an existing key counts as access — recency must refresh, value must overwrite.
Storing values instead of node references in the map — eviction then becomes O(n).

Follow-up questions

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

Add TTL (time-to-live) per key with lazy expiration.
Make it thread-safe.
Implement LFU (Least Frequently Used) instead — LeetCode 460.
What if you also need O(1) for getMostRecent() and getLeastRecent() snapshots?
Distributed LRU across multiple cache nodes — consistent hashing.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Will Shopify accept the JavaScript Map shortcut?

Most interviewers accept it if you explicitly call out the underlying data structures (hash map + insertion-ordered linked list inside V8's Map implementation). Safer move: write the Map version first, then offer to expand to the explicit doubly-linked-list version if asked.

Why sentinel head/tail nodes?

They eliminate the need to special-case insert-at-empty or remove-the-only-node. Every real node always has a non-null prev and next, so _remove and _addToFront become four unconditional pointer assignments. Robustness under time pressure.

Free learning resources

Curated free links for this problem.