Skip to main content

18. LRU Cache

mediumAsked at Autodesk

Design a cache that evicts the least recently used key when capacity is exceeded.

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

Problem

Design and implement an LRU cache with capacity. Support get(key) returning the value if present (and marking it most recently used), and put(key, value) which inserts or updates and evicts the least recently used key when over capacity. Both operations should run in O(1).

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key, value <= 10^9
  • up to 2*10^5 operations

Examples

Example 1

Input
ops=["LRUCache","put","put","get","put","get"], args=[[2],[1,1],[2,2],[1],[3,3],[2]]
Output
[null,null,null,1,null,-1]

Example 2

Input
capacity=1; put(1,1); put(2,2); get(1)
Output
-1

Approaches

1. Array of (key,value) with reorder

Store a list of entries; on access move to the front.

Time
O(n) per op
Space
O(n)
// list.indexOf + splice is O(n); fine for tiny capacities but not for the constraint here.

Tradeoff:

2. Hash map + JS Map insertion order

JavaScript's Map preserves insertion order. delete-and-set on get/put pushes the key to the end; on overflow remove the first (oldest) key.

Time
O(1) amortized
Space
O(capacity)
class LRUCache {
  constructor(capacity) { this.cap = capacity; this.map = new Map(); }
  get(key) {
    if (!this.map.has(key)) return -1;
    const v = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, v);
    return v;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.cap) this.map.delete(this.map.keys().next().value);
  }
}

Tradeoff:

Autodesk-specific tips

Autodesk uses LRU caches for tessellated mesh/render fragments, so a constant-time put/get implementation is expected on follow-ups.

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

Practice these live with InterviewChamp.AI →