Skip to main content

20. LRU Cache

mediumAsked at Roblox

Design a fixed-capacity cache that evicts the least recently used item — the exact structure Roblox's asset server uses to keep hot game assets in memory while dropping stale ones as thousands of players load different virtual worlds.

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

Problem

Design a data structure that follows the LRU (Least Recently Used) cache eviction policy. Implement the LRUCache class with a constructor that accepts capacity, a get(key) method returning the value or -1, and a put(key, value) method. 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: get(2) returns -1 after key 2 was evicted when key 3 was inserted at capacity.

Approaches

1. Brute force — Map with sorted access tracking

Use a Map to store values and a separate array to track access order. O(n) eviction because finding the LRU requires scanning the access array.

Time
O(n) per put worst case
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
    this.order = [];
  }

  _touch(key) {
    const idx = this.order.indexOf(key);
    if (idx !== -1) this.order.splice(idx, 1);
    this.order.push(key);
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    this._touch(key);
    return this.map.get(key);
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.map.set(key, value);
      this._touch(key);
      return;
    }
    if (this.map.size >= this.cap) {
      const lru = this.order.shift();
      this.map.delete(lru);
    }
    this.map.set(key, value);
    this.order.push(key);
  }
}

Tradeoff:

2. Optimal — HashMap + doubly linked list

Maintain a doubly linked list for O(1) node removal and a HashMap for O(1) node lookup. Most-recently-used at tail, least-recently-used at head. JS Map preserves insertion order, giving an equivalent O(1) implementation using delete-and-re-insert.

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

Tradeoff:

Roblox-specific tips

Roblox interviews test LRU because asset caches are central to the streaming architecture. Know that JS Map insertion-order trick cold — interviewers are impressed when you spot it. They'll also push you toward a raw doubly-linked-list implementation to verify you understand pointer manipulation, which mirrors how Roblox's C++ engine layer handles the same structure.

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

Practice these live with InterviewChamp.AI →