Skip to main content

16. LRU Cache

mediumAsked at Dropbox

Design a fixed-capacity cache that evicts the least-recently-used entry — Dropbox's sync engine relies on this exact policy to keep hot file metadata in memory without blowing heap budgets.

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 takes capacity as input, a get(key) method that returns the value if the key exists (otherwise -1), and a put(key, value) method that inserts or updates a key-value pair, evicting the least recently used key when capacity is exceeded. 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), key 2 is evicted. After put(4,4), key 1 is evicted. get(1) returns -1, get(3) and get(4) return 3 and 4.

Example 2

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

Approaches

1. Brute force (array eviction)

Track insertion order in an array; on every access, scan and move the entry to the front. Eviction is easy but access is O(n).

Time
O(n)
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.order = [];
    this.map = new Map();
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    this.order = this.order.filter(k => k !== key);
    this.order.push(key);
    return this.map.get(key);
  }
  put(key, value) {
    if (this.map.has(key)) {
      this.order = this.order.filter(k => k !== key);
    } else if (this.order.length === this.capacity) {
      const lru = this.order.shift();
      this.map.delete(lru);
    }
    this.order.push(key);
    this.map.set(key, value);
  }
}

Tradeoff:

2. Hash map + doubly-linked list

Combine a Map for O(1) lookup with a doubly-linked list to track recency. Move nodes to the head on access; evict from the tail. Both operations are O(1).

Time
O(1)
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    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)) {
      this._remove(this.map.get(key));
    } 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:

Dropbox-specific tips

Dropbox interviewers care about the O(1) constraint — they'll probe whether you reach for a doubly-linked list unprompted. Explain why a singly-linked list fails (you can't delete a tail predecessor in O(1)), then walk the sentinel-head/tail trick that eliminates null checks.

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

Practice these live with InterviewChamp.AI →