Skip to main content

13. LRU Cache

mediumAsked at Postman

Design a least-recently-used cache with O(1) get and put.

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

Problem

Design a data structure that follows the LRU policy. Implement get(key) and put(key, value); both must run in O(1) average time and evict the least-recently-used entry when capacity is exceeded.

Constraints

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

Examples

Example 1

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

Example 2

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

Approaches

1. Array scan

Store entries in an array and move-to-front on access; eviction pops the tail.

Time
O(n) per op
Space
O(n)
// linear scan to find key, splice, re-push — easy but slow

Tradeoff:

2. Map preserving insertion order

JavaScript's Map iterates in insertion order; on access delete+reinsert to move to most-recent; on overflow drop the first key the iterator yields.

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

Tradeoff:

Postman-specific tips

Postman cares about LRU mechanics because their response cache and recently-used environment list use exactly this eviction shape — get fluent with the Map idiom.

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

Practice these live with InterviewChamp.AI →