Skip to main content

26. LRU Cache

mediumAsked at Figma

Design a data structure that follows the Least Recently Used (LRU) cache eviction policy, supporting O(1) get and put operations. Figma asks this to probe how candidates reason about spatial-data caching — the same mechanism that keeps recently-rendered canvas tiles hot in memory.

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

Source citations

Public interview reports confirming this problem appears in Figma loops.

  • Glassdoor (2025)— Reported in Figma SWE II loop; interviewer asked to extend to multi-threaded scenario after base solution.
  • LeetCode Discuss (2026)— Multiple Figma candidates confirmed LRU Cache appears in design-adjacent coding rounds.
  • Blind (2025)— Figma staff engineer noted they care about explaining the doubly-linked list choice, not just code correctness.

Problem

Design and implement a data structure for an LRU (Least Recently Used) cache. It should support get(key) — return the value of the key if it exists, otherwise return -1 — and put(key, value) — insert or update the value; if the cache reaches its capacity, evict the least recently used item before inserting. Both operations 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
[null,null,null,1,null,-1,null,1,3,4]

Explanation: After put(3,3) with capacity 2, key 2 is evicted (LRU). After put(4,4), key 1 was most recently used via get(1), so key 3 is evicted.

Example 2

Input
LRUCache(1); put(2,1); get(2); put(3,2); get(2); get(3)
Output
[null,null,1,null,-1,2]

Explanation: Capacity 1: each put evicts the single existing entry; get(2) after put(3,2) returns -1.

Approaches

1. Brute force — ordered map / array scan

Keep all entries in an array, tracking insertion/access timestamps. On eviction, scan to find the entry with the smallest timestamp.

Time
O(n) per get/put
Space
O(n)
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.entries = []; // [{key, value, time}]
    this.clock = 0;
  }
  get(key) {
    const e = this.entries.find(e => e.key === key);
    if (!e) return -1;
    e.time = ++this.clock;
    return e.value;
  }
  put(key, value) {
    const e = this.entries.find(e => e.key === key);
    if (e) { e.value = value; e.time = ++this.clock; return; }
    if (this.entries.length === this.capacity) {
      let minIdx = 0;
      for (let i = 1; i < this.entries.length; i++)
        if (this.entries[i].time < this.entries[minIdx].time) minIdx = i;
      this.entries.splice(minIdx, 1);
    }
    this.entries.push({ key, value, time: ++this.clock });
  }
}

Tradeoff: O(n) scan per operation makes this unacceptable for any real cache; fails at 2×10^5 operations.

2. Doubly-linked list + HashMap

Maintain a HashMap for O(1) key lookup and a doubly-linked list to track access order — head = most recent, tail = least recent. On get or put, move the node to the head; on eviction, remove from the tail. Both operations are O(1) because HashMap gives the node pointer directly and list operations on a known node are O(1).

Time
O(1) amortized for both get and put
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(); // key -> Node
    // sentinel head (MRU side) and tail (LRU side)
    this.head = new Node(0, 0);
    this.tail = new Node(0, 0);
    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));
    } else if (this.map.size === this.cap) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
    const node = new Node(key, value);
    this._insertFront(node);
    this.map.set(key, node);
  }
}

Tradeoff: Sentinel head/tail nodes eliminate all null checks on boundary conditions. The key insight is that HashMap stores Node references, so list manipulation never requires a search — every pointer adjustment is direct.

Figma-specific tips

Figma interviewers focus on whether you can articulate *why* the doubly-linked list is necessary (single-linked can't remove a node in O(1) without traversal) and connect the pattern to real canvas-rendering concerns — e.g., tile caches for a multiplayer canvas where each collaborator's viewport evicts tiles the current user isn't seeing. Bonus signal: mention thread-safety considerations relevant to Figma's real-time CRDT sync layer, even if the interviewer doesn't ask — it shows awareness of their concurrency model. They grade on clarity of the eviction invariant, not lines of code.

Common mistakes

  • Using a singly-linked list and scanning backward to find the predecessor on eviction — defeats O(1) guarantee.
  • Forgetting to delete the evicted key from the HashMap, causing a stale reference that inflates memory and breaks size accounting.
  • Off-by-one on capacity check: checking `size > capacity` after insert instead of `size === capacity` before insert, causing momentary over-capacity.
  • Not moving the node to the front on put when the key already exists — treating put as write-only and skipping the recency update.

Follow-up questions

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

  • How would you make this LRU cache thread-safe for Figma's multi-client sync server? What granularity of locking would you choose?
  • Extend to an LFU (Least Frequently Used) cache. How does the data structure change?
  • Figma needs to cache quadtree nodes for a canvas with 10 million objects. How would you adapt this structure — what's your eviction unit and how does capacity sizing change?
  • If get and put are called concurrently from 100 goroutines, what's the minimal change to make this correct without a global lock?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why not just use JavaScript's Map, which preserves insertion order?

JavaScript's built-in Map does maintain insertion order and its keys() iterator returns them in that order, so you can use Map alone as an LRU: delete-and-reinsert on access to move a key to the end, and delete the first key (map.keys().next().value) on eviction. Both operations are O(1) in modern engines. The doubly-linked-list + HashMap approach is language-agnostic and often expected in interviews to demonstrate understanding of the underlying mechanism.

Does the sentinel (dummy) head/tail pattern matter?

Yes — sentinel nodes eliminate six conditional null checks (for empty list, head insert, tail removal) that would otherwise make the code error-prone. Interviewers at companies like Figma notice when you use sentinels because it signals you've internalized the pattern, not just memorized it. Always initialize with sentinels pointing to each other.

Why is this relevant to Figma specifically?

Figma's multiplayer canvas maintains in-memory caches for rendered tiles, resolved CRDT operations, and computed layout nodes. LRU eviction is the canonical policy for spatial caches where recently-viewed regions are most likely to be revisited. Understanding LRU deeply helps Figma engineers reason about memory pressure in multi-user sessions with large canvases.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →