Skip to main content

146. LRU Cache

mediumAsked at Google

Design a cache that evicts the least recently used key when full. Google asks this to test whether you reach for the doubly-linked-list + hash map combo and can articulate why neither data structure alone gives you O(1) for both get and put.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Recurring Google L4/L5 onsite question (data-structure design round).
  • Reddit r/cscareerquestions (2025-12)— Multiple Google new-grad onsite reports cite LRU as the data-structure design round.

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), key 2 is evicted because it was least recently used.

Approaches

1. Hash map + insertion-ordered Map iteration

JavaScript's Map preserves insertion order. Delete + re-insert on get to refresh recency; iterate 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: Pragmatic and ships in 15 lines if the language has insertion-ordered maps. Most interviewers count this as the optimal because the underlying complexity is the same. Mention it before the doubly-linked-list version so they know you noticed the language feature.

2. Doubly linked list + hash map (canonical optimal)

Hash map from key to node pointer + doubly linked list with sentinel head/tail. Move-to-front on 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); // most recent
    this.tail = new Node(0, 0); // least recent
    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 and what most interviewers expect when they ask 'don't rely on language built-ins.' Sentinel nodes eliminate the null-check branches that break candidates under time pressure.

Google-specific tips

Google interviewers grade this on two axes: (1) you reach for both data structures together and can explain why neither alone works (hash map alone has no order; linked list alone has no O(1) lookup); (2) sentinel head/tail to eliminate edge cases. If you forget sentinels and the interviewer points out a null deref, you can recover, but bringing them up unprompted scores a higher bar.

Common mistakes

  • Using a singly linked list — you need O(1) node removal, which requires the prev pointer.
  • Forgetting to remove the evicted key from the hash map (memory leak).
  • Off-by-one on capacity check: should evict when size >= capacity, before insert, not after.
  • Forgetting that put on an existing key counts as access — recency must refresh.

Follow-up questions

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

  • Make it thread-safe.
  • Add TTL (time-to-live) per key.
  • Implement LFU (Least Frequently Used) instead.
  • What if you also need O(1) for getMostRecent() and getLeastRecent() snapshots?

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 not just use an array?

Move-to-front on an array is O(n) because you have to shift elements. The hash map gives O(1) lookup, and the doubly linked list gives O(1) splice.

Will Google accept the JavaScript Map shortcut?

It depends on the interviewer. Some count it as the elegant answer; others ask for the underlying data structures. Safer to mention the Map version, then volunteer the linked-list version to demonstrate both.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →