146. LRU Cache

Q: Why doubly-linked, not singly-linked?

To remove an arbitrary node in O(1), you need a pointer to its predecessor. A singly-linked list requires O(n) traversal to find it.

Q: Why dummy head and tail?

They eliminate null-checks for inserting at the head or removing from the tail. Every operation becomes uniform pointer rewiring.

Q: Is the JS Map approach acceptable at Linear?

Usually yes — but state upfront that you're relying on JS Map's insertion-order guarantee (per the ECMAScript spec). Then offer to implement the explicit DLL version if they prefer.

mediumAsked at Linear

Design a cache that evicts the least-recently-used item when it's full. Linear asks this because it's a real design problem embedded in a coding question — you need to compose a hash map and a doubly-linked list to hit O(1) get and put.

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

Source citations

Public interview reports confirming this problem appears in Linear loops.

Glassdoor (2026-Q1)— Cited as a design-heavy coding problem in Linear SWE onsite reports.
Blind (2025-11)— Multiple Linear threads list LRU Cache as a high-signal medium question testing data structure composition.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(capacity) initializes the LRU cache with a 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 if the key exists, otherwise inserts the key-value pair. When the number of keys exceeds the 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

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

Explanation: After put(3,3), key 2 is evicted (least recently used). After put(4,4), key 1 (not 3, since get(1) made it recent) is not evicted — key 2 was already gone, so key 3 is evicted.

Approaches

1. Ordered Map (built-in)

Use JavaScript's Map which preserves insertion order. On access, delete and re-insert to make the key 'most recent'. Evict the first key in the map (least recent).

Time: O(1) get and put
Space: O(capacity)

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }
  get(key) {
    if (!this.cache.has(key)) return -1;
    const val = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, val); // move to end (most recent)
    return val;
  }
  put(key, value) {
    if (this.cache.has(key)) this.cache.delete(key);
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      this.cache.delete(this.cache.keys().next().value); // evict LRU (first key)
    }
  }
}

Tradeoff: O(1) amortized because JS Map's delete/set and keys().next() are all O(1). A great practical answer in JavaScript. However, interviewers often want the explicit doubly-linked-list version to demonstrate understanding of the data structure.

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

A Map gives O(1) key lookup; a doubly-linked list gives O(1) move-to-front and evict-from-tail. The map stores key → node pointers.

Time: O(1) get and put
Space: O(capacity)

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

Tradeoff: Explicit O(1) for all operations, no reliance on language-specific Map insertion order. This is the canonical answer Linear expects when they say 'don't use built-in ordered structures.'

Linear-specific tips

Start by explaining the data structure composition before writing any code: 'I need O(1) lookup — hash map. I need O(1) move-to-front and eviction — doubly-linked list. Combining them is the textbook LRU cache design.' Linear values architectural thinking. Use dummy head and tail nodes to eliminate edge cases in the linked-list operations.

Common mistakes

Using a singly-linked list — you can't remove a node in O(1) without a pointer to its predecessor.
Forgetting to delete the evicted node from the map — the map and list must stay in sync.
Not moving the node to the front on a get() call — a cache hit counts as a recent use.
Skipping dummy head/tail — every insert/remove then requires special-casing the empty list.

Follow-up questions

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

LFU Cache (LC 460) — evict the least-frequently-used item; requires tracking frequency buckets.
How would you implement this in a thread-safe manner?
What if capacity changes dynamically after construction?

Solve it now

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