Skip to main content

15. LRU Cache

mediumAsked at Nubank

Design a Least-Recently-Used cache with O(1) get and put; a staple Nubank uses to probe whether candidates can pair a hash map with a doubly-linked list for hot-account caching.

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

Problem

Design an LRU cache with capacity. get(key) returns the value or -1 if missing and marks the key most-recently-used. put(key, value) inserts/updates, evicting the least-recently-used entry when capacity is exceeded.

Constraints

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

Examples

Example 1

Input
['LRUCache','put','put','get','put','get','put','get','get','get'][[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
Output
[null,null,null,1,null,-1,null,-1,3,4]

Example 2

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

Approaches

1. OrderedMap via JS Map

Use Map insertion-order; on get, delete and re-set to push to tail.

Time
O(1) amortized
Space
O(capacity)
class LRUCache{constructor(c){this.c=c;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.c) this.m.delete(this.m.keys().next().value);}}

Tradeoff:

2. HashMap + doubly-linked list

Explicit DLL gives true O(1) move-to-front; the map points key -> node so eviction at the tail is constant-time.

Time
O(1)
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
    this.head = { prev: null, next: null };
    this.tail = { prev: this.head, next: null };
    this.head.next = this.tail;
  }
  _remove(n) { n.prev.next = n.next; n.next.prev = n.prev; }
  _addFront(n) { n.next = this.head.next; n.prev = this.head; this.head.next.prev = n; this.head.next = n; }
  get(k) {
    if (!this.map.has(k)) return -1;
    const n = this.map.get(k); this._remove(n); this._addFront(n); return n.val;
  }
  put(k, v) {
    if (this.map.has(k)) { this._remove(this.map.get(k)); }
    const n = { key: k, val: v }; this._addFront(n); this.map.set(k, n);
    if (this.map.size > this.cap) {
      const lru = this.tail.prev; this._remove(lru); this.map.delete(lru.key);
    }
  }
}

Tradeoff:

Nubank-specific tips

Nubank often follows up with: now make it thread-safe for concurrent card-auth reads — be ready to discuss a striped lock or a sharded LRU per BIN range.

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

Practice these live with InterviewChamp.AI →