Skip to main content

20. LRU Cache

mediumAsked at Box

Design a Least Recently Used cache with O(1) get and put — Box engineers face this exact tradeoff when caching frequently accessed file metadata and thumbnail previews across their enterprise CDN.

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

Problem

Design a data structure that follows the Least Recently Used (LRU) cache eviction policy. Implement the LRUCache class with a constructor that accepts capacity as an integer. Implement get(key) which returns the value of the key if it exists, otherwise -1. Implement put(key, value) which inserts or updates the key-value pair. If the cache reaches capacity, evict the least recently used key before inserting the new key. 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 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 so key 2 (least recently used) is evicted. get(2) returns -1.

Approaches

1. Brute force — ordered map

Use a plain Map and track insertion order; on eviction, find the key with the oldest access timestamp by scanning all entries.

Time
O(n) per operation
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map(); // key -> {value, time}
    this.time = 0;
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    this.map.get(key).time = ++this.time;
    return this.map.get(key).value;
  }
  put(key, value) {
    if (this.map.has(key)) {
      this.map.get(key).value = value;
      this.map.get(key).time = ++this.time;
      return;
    }
    if (this.map.size === this.capacity) {
      let lruKey = null, minTime = Infinity;
      for (const [k, v] of this.map) {
        if (v.time < minTime) { minTime = v.time; lruKey = k; }
      }
      this.map.delete(lruKey);
    }
    this.map.set(key, { value, time: ++this.time });
  }
}

Tradeoff:

2. Optimal — doubly linked list + hash map

Combine a hash map for O(1) lookup with a doubly linked list to maintain recency order. Move nodes to the front on access; evict from the tail.

Time
O(1)
Space
O(capacity)
class DLLNode {
  constructor(key, val) {
    this.key = key; this.val = val;
    this.prev = this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    // sentinel head (MRU side) and tail (LRU side)
    this.head = new DLLNode(0, 0);
    this.tail = new DLLNode(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)) {
      const node = this.map.get(key);
      node.val = value;
      this._remove(node);
      this._insertFront(node);
      return;
    }
    if (this.map.size === this.capacity) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
    const node = new DLLNode(key, value);
    this._insertFront(node);
    this.map.set(key, node);
  }
}

Tradeoff:

Box-specific tips

Box interviewers pay close attention to how you handle the eviction pointer — they want to see you name 'doubly linked list' before you code it, then explain why singly linked won't work. Connecting this to Box's thumbnail and metadata caching layer earns you extra signal: the same get/put contract runs at millions of QPS against their content delivery infrastructure.

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

Practice these live with InterviewChamp.AI →