Skip to main content

146. LRU Cache

mediumAsked at Apple

LRU Cache is Apple's flagship data-structure design medium. The answer is a hash map for O(1) lookup plus a doubly linked list for O(1) move-to-front. Apple specifically grades on whether you handle the pointer surgery without leaving a dangling neighbor.

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

Source citations

Public interview reports confirming this problem appears in Apple loops.

  • Glassdoor (2026-Q1)— Apple SWE phone-screen + onsite reports consistently list LRU Cache as the most-repeated data-structure design medium.
  • Blind (2025-12)— Apple ICT3/ICT4 reports cite LRU Cache as a recurring 30-45 minute interview.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity) initialize the LRU cache with positive size capacity. int get(int key) return the value of the key if the key exists, otherwise return -1. void put(int key, int value) update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, 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. Hash map + doubly linked list (optimal)

Map key to a list node. List is ordered most-recent-first. On get, move the node to the head. On put, insert at head; if over capacity, drop the tail.

Time
O(1) per operation
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
    // doubly linked list with dummy head and tail
    this.head = { key: 0, val: 0, prev: null, next: null };
    this.tail = { key: 0, val: 0, 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;
  }
  _addToFront(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._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.cap) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
    const node = { key, val: value, prev: null, next: null };
    this._addToFront(node);
    this.map.set(key, node);
  }
}

Tradeoff: True O(1) per op. The dummy head and tail eliminate every empty-list edge case. The map is the only way to get O(1) lookup; the doubly linked list is the only way to get O(1) move-to-front. Both are necessary.

2. Map insertion-order trick (LinkedHashMap analog)

In JS, Map preserves insertion order. On get, delete + re-insert to move to back. On eviction, delete the first key.

Time
O(1) per operation
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.cap = 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.cap) {
      const oldestKey = this.map.keys().next().value;
      this.map.delete(oldestKey);
    }
    this.map.set(key, value);
  }
}

Tradeoff: Works because JavaScript's Map has guaranteed insertion-order iteration. Java's LinkedHashMap and Python's OrderedDict have the same property. Apple will accept this AND ask you to also write the doubly-linked-list version — they want to know you can do the pointer surgery.

Apple-specific tips

Apple is grading two things: (1) can you NAME why you need both data structures, and (2) can you implement the doubly linked list with dummy head/tail to avoid edge cases. Say out loud: 'I need O(1) lookup by key (map) AND O(1) move-to-front (doubly linked list). Map alone is O(1) lookup but O(n) reorder; list alone is O(1) reorder but O(n) lookup. Combined, both ops are O(1).' That paragraph is the entire 30-minute interview.

Common mistakes

  • Using a singly linked list — can't remove a middle node in O(1).
  • Forgetting to store key on the node — needed for the eviction step (to delete from the map).
  • Not using dummy head/tail — produces 4 edge cases (empty list, single node, head, tail) that each have their own pointer-fix bug.

Follow-up questions

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

  • LFU Cache (LC 460) — least-frequently-used, harder.
  • Design In-Memory File System (LC 588).
  • What if the cache had to be thread-safe? (Sharded by key, or read-write lock.)

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

Because we need to remove a NODE FROM THE MIDDLE of the list in O(1). With a singly linked list, finding the predecessor is O(n).

Map-insertion-order or doubly linked list?

In an interview, write the doubly linked list version. The map-order trick is a real-world shortcut but Apple wants to see you can implement the pointer surgery.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →