Skip to main content

25. LRU Cache

mediumAsked at Instacart

Design a cache that evicts the least recently used item when full — Instacart caches store inventory snapshots in memory for sub-millisecond catalog reads; LRU eviction keeps the hottest stores resident.

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

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with a fixed capacity: get(key) returns the value if the key exists (and marks it recently used), otherwise -1; put(key, value) inserts or updates the key, evicting the least recently used key if capacity is exceeded.

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 cache = new LRUCache(2); cache.put(1,1); cache.put(2,2); cache.get(1); cache.put(3,3); cache.get(2); cache.put(4,4); cache.get(1); cache.get(3); cache.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. HashMap + ordered iteration

Use a Map (preserves insertion order in JS) as an ordered hash map. On get/put, delete and re-insert the key to make it most recent. Evict the first (oldest) entry when over capacity.

Time
O(1) amortized per get/put
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:

2. Doubly linked list + HashMap

Store nodes in a doubly linked list (most recent at tail, least recent at head) and maintain a HashMap from key to node. O(1) move-to-tail on access; O(1) evict head.

Time
O(1) per get/put
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
    this.head = { key: null, val: null, prev: null, next: null };
    this.tail = { key: null, val: null, 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;
  }

  _insertTail(node) {
    node.prev = this.tail.prev;
    node.next = this.tail;
    this.tail.prev.next = node;
    this.tail.prev = node;
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node);
    this._insertTail(node);
    return node.val;
  }

  put(key, value) {
    if (this.map.has(key)) this._remove(this.map.get(key));
    const node = { key, val: value, prev: null, next: null };
    this._insertTail(node);
    this.map.set(key, node);
    if (this.map.size > this.cap) {
      const lru = this.head.next;
      this._remove(lru);
      this.map.delete(lru.key);
    }
  }
}

Tradeoff:

Instacart-specific tips

Instacart's catalog service caches store inventory at the API layer. The JavaScript Map approach is the pragmatic answer interviewers accept, but the doubly linked list version shows systems depth — expect a follow-up asking why you need the node to store its own key (needed to delete from the HashMap when evicting from the list head).

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 Instacart interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →