Skip to main content

22. LRU Cache

mediumAsked at Wix

Build a fixed-capacity cache that evicts the least recently used entry — Wix uses LRU as the eviction policy for rendered-widget caches and undo-history buffers in the site editor, making this a core design pattern for the team.

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

Problem

Design a data structure that follows the Least Recently Used (LRU) cache constraint. Implement LRUCache with capacity, get(key) returning the value or -1 if missing, and put(key, value) inserting or updating a key-value pair and evicting the LRU key when over capacity. 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: put(3,3) evicts key 2 (LRU). put(4,4) evicts key 1 (LRU after get(2) failed). get(1) = -1 (evicted).

Approaches

1. Map with reinsert trick

Use a JavaScript Map which maintains insertion order. On access, delete and reinsert the key to move it to the end. Evict from the front (oldest).

Time
O(1) amortised
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.capacity = 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.capacity) {
      const lruKey = this.map.keys().next().value;
      this.map.delete(lruKey);
    }
  }
}

Tradeoff:

2. HashMap + doubly linked list

Maintain a doubly linked list in recency order with sentinel head/tail nodes, plus a hashmap from key to node. get/put move nodes to the tail in O(1); eviction removes from the head.

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

Tradeoff:

Wix-specific tips

Wix interviewers use this to assess whether you can compose two simple data structures into one complex invariant. Start with the Map trick — it's clean and idiomatic JS — then offer the doubly linked list if they ask for a stricter O(1) guarantee or for something that ports to a language without ordered maps.

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

Practice these live with InterviewChamp.AI →