Skip to main content

20. LRU Cache

mediumAsked at Revolut

Design an O(1) get and put cache with least-recently-used eviction, a Revolut systems-design staple that mirrors caching the hottest FX rates with strict memory bounds.

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

Problem

Implement an LRU cache supporting get(key) and put(key, value) in O(1) average time, evicting the least recently used entry when capacity is exceeded. get and put must both count as accesses for LRU ordering.

Constraints

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

Examples

Example 1

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

Example 2

Input
cap=2; put(1,1); put(2,2); put(1,10); get(1)
Output
10

Approaches

1. Map + array

Use a Map and a JS array for ordering; reorder on access (O(n) per access).

Time
O(n)
Space
O(n)
// on get/put, splice the key out and push back to the tail of the array

Tradeoff:

2. Hash map + doubly linked list

Map key to node; doubly linked list orders by recency. Move-to-head on access; evict from tail when over capacity. Average O(1) per op.

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

Tradeoff:

Revolut-specific tips

Revolut graders will ask you to justify why the JS-Map insertion-order trick is genuinely O(1) — they want to hear that Map.prototype.delete + set has amortized constant time, the same property a doubly linked list provides explicitly.

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

Practice these live with InterviewChamp.AI →