Skip to main content

18. LRU Cache

mediumAsked at Freshworks

Design an O(1) least-recently-used cache — Freshworks asks this verbatim because their multi-tenant ticket cache is exactly this data structure.

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

Problem

Design a data structure that supports get(key) and put(key, value) in O(1) average time, evicting the least-recently-used key when capacity is exceeded.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key, value <= 10^4
  • Up to 2 * 10^5 calls

Examples

Example 1

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

Example 2

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

Approaches

1. Brute force (array scan)

Store entries in an array; on access, move to end. Eviction = shift from front. O(n) per op.

Time
O(n) per op
Space
O(n)
class LRUCache { constructor(cap){this.cap=cap;this.arr=[]} /* scan for key, splice, push */ }

Tradeoff:

2. Map preserves insertion order

JS Map keeps insertion order. On get, delete + reinsert so the key is freshest. On put past capacity, evict map.keys().next().value (the oldest).

Time
O(1) average per op
Space
O(capacity)
class LRUCache {
  constructor(capacity) { this.capacity = 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);
    else if (this.map.size >= this.capacity) this.map.delete(this.map.keys().next().value);
    this.map.set(key, value);
  }
}

Tradeoff:

Freshworks-specific tips

Freshworks will probe whether you know the canonical doubly-linked-list + hash-map design — even if you ship the Map shortcut, sketch the DLL diagram so they see you understand the underlying primitive.

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

Practice these live with InterviewChamp.AI →