Skip to main content

21. LRU Cache

mediumAsked at Coinbase

Build a fixed-capacity account-data cache that evicts the least-recently-used entry — Coinbase uses this design question to measure whether you can combine a hash map and a doubly-linked list for O(1) reads and writes.

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

Problem

Design a data structure that follows a Least Recently Used cache eviction policy. Implement LRUCache(capacity), get(key) returning the value or -1 if absent, and put(key, value) inserting or updating the key. When the cache reaches capacity, evict the least recently used key before inserting. Both get and put must run in O(1) average time.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • At most 2 * 10^5 calls 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: After put(3,3) key 2 is evicted (LRU). After put(4,4) key 1 is evicted.

Approaches

1. Map + doubly-linked list

Hash map for O(1) key lookup; doubly-linked list to track recency. Move accessed node to head; evict tail on overflow.

Time
O(1)
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.cap = capacity;
    this.map = new Map();
    this.head = new Node(0, 0); // MRU sentinel
    this.tail = new Node(0, 0); // LRU sentinel
    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.map.set(key, node);
    this._insertFront(node);
    if (this.map.size > this.cap) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
  }
}

Tradeoff:

2. JavaScript Map insertion-order trick

JS Map preserves insertion order. On access, delete and re-insert the key to make it most-recent. Evict the first key (Map.keys().next()) on overflow.

Time
O(1) amortised
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);
    this.map.set(key, value);
    if (this.map.size > this.cap) {
      this.map.delete(this.map.keys().next().value);
    }
  }
}

Tradeoff:

Coinbase-specific tips

Coinbase often asks this in the context of a wallet-balance cache or order-status cache. They want the doubly-linked-list implementation first — it shows you understand the data structure from first principles. Mentioning the JS Map shortcut is a bonus that demonstrates language fluency, but Coinbase graders deduct points if it is your only answer, because it hides the real mechanics.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →