Skip to main content

24. LRU Cache

mediumAsked at Etsy

Build a Least Recently Used cache with O(1) get and put — the exact eviction policy Etsy uses for its listing-detail cache to keep hot products in memory without unbounded growth.

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: LRUCache(capacity) initializes the LRU cache with positive size capacity. get(key) returns the value of the key if it exists, otherwise -1. put(key, value) updates the value if the key exists. Otherwise, adds the key-value pair. When the cache reaches its capacity, evict the least recently used key before inserting a new one. get and put must each 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

Example 2

Input
LRUCache(1), put(2,1), get(2), put(3,2), get(2), get(3)
Output
1, -1, 2

Approaches

1. Ordered map (JavaScript Map insertion order)

JavaScript's Map preserves insertion order. To mark a key as most-recently-used, delete it and re-insert it. The first key in the Map is always the LRU. get and put are O(1) amortized.

Time
O(1) 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); // move to end (most recent)
    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) {
      const lruKey = this.map.keys().next().value;
      this.map.delete(lruKey);
    }
  }
}

Tradeoff:

2. Hash map + doubly linked list

The canonical O(1) implementation: a HashMap stores key → node pointers; a doubly linked list orders nodes by recency (head = MRU, tail = LRU). get moves a node to head. put inserts at head and, when over capacity, removes from tail. Both operations are O(1).

Time
O(1) per get/put
Space
O(capacity)
class Node {
  constructor(k, v) {
    this.key = k; this.val = v;
    this.prev = this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
    this.head = new Node(0, 0); // dummy MRU
    this.tail = new Node(0, 0); // dummy LRU
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  _insertAtHead(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._insertAtHead(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._insertAtHead(node);
    if (this.map.size > this.cap) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
  }
}

Tradeoff:

Etsy-specific tips

Etsy's caching layer for listing thumbnails uses LRU. Interviewers here ask the JavaScript-Map shortcut first to gauge awareness of language primitives, then switch to the doubly-linked-list requirement to see if you can implement O(1) deletion without language help. Know both paths. Also expect a follow-up: 'how would you make this thread-safe?' — answer with a read-write lock or a concurrent cache library.

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

Practice these live with InterviewChamp.AI →