Skip to main content

146. LRU Cache

hardAsked at Canva

Design a Least Recently Used cache with O(1) get and put — Canva's image and font rendering pipeline uses LRU eviction to cap memory on large canvases, making this a direct system-design-in-code test you'll likely see in a senior loop.

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

Problem

Design a data structure that follows the Least Recently Used (LRU) cache constraint. Implement the LRUCache class with a fixed capacity: get(key) returns the value if the key exists (and marks it as recently used), or -1 if it does not. put(key, value) inserts or updates the key-value pair; if the cache is at capacity, evict the least recently used key first. 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 will be made 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) the cache is full and key 2 (least recently used) is evicted. put(4,4) then evicts key 1 — but get(1) ran after put(1,1) making 1 more recent than 2, so 2 is evicted first.

Approaches

1. OrderedMap / Map insertion order

JavaScript's Map preserves insertion order; simulate recency by deleting and re-inserting a key on every access, then evict the first (oldest) entry when over capacity.

Time
O(1) amortized
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); // 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.capacity) {
      // delete the first (least recently used) key
      this.map.delete(this.map.keys().next().value);
    }
  }
}

Tradeoff:

2. Optimal (HashMap + doubly linked list)

Maintain a HashMap for O(1) key lookup and a doubly linked list for O(1) order tracking — move-to-front on access, remove-from-tail on eviction; no reliance on language-specific Map ordering.

Time
O(1)
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    // Sentinel head and tail nodes
    this.head = { key: 0, val: 0, prev: null, next: null };
    this.tail = { key: 0, val: 0, 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;
  }
  _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)) {
      const node = this.map.get(key);
      node.val = value;
      this._remove(node);
      this._insertFront(node);
    } else {
      if (this.map.size === this.capacity) {
        const lru = this.tail.prev;
        this._remove(lru);
        this.map.delete(lru.key);
      }
      const node = { key, val: value, prev: null, next: null };
      this._insertFront(node);
      this.map.set(key, node);
    }
  }
}

Tradeoff:

Canva-specific tips

Canva caches decoded image bitmaps and font glyph atlases — both are large, and the eviction policy directly affects canvas render performance. In the interview, present both approaches: the JS Map insertion-order trick is quick to code and passes every test, but mention upfront that it relies on a language-specific guarantee not available in Java/Python without LinkedHashMap/OrderedDict. The doubly-linked-list approach is language-agnostic and is what interviewers want to see for senior roles. Draw the sentinel-head/sentinel-tail structure before coding — it eliminates all the 'is the list empty?' edge cases.

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

Practice these live with InterviewChamp.AI →