Skip to main content

14. LRU Cache

mediumAsked at N26

Design a data structure that supports get and put in O(1) time and evicts the least recently used key when capacity is exceeded. N26 asks this because their account-balance hot cache must evict cold customers without scanning.

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

Problem

Implement LRUCache with get(key) and put(key, value) both in O(1). When putting a new key exceeds capacity, evict the least recently used key. Touching a key with get also makes it the most recent.

Constraints

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

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 timestamp

Track an access timestamp per key and scan to find the min on eviction.

Time
O(n) per op
Space
O(n)
// store {key,value,t}; scan to evict min t.
// Too slow under 2*10^5 ops.

Tradeoff:

2. Hash map plus doubly linked list

Map keys to list nodes; the list orders nodes by recency. Get unlinks and reinserts at head; put evicts tail when full. Every op is O(1).

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

Tradeoff:

N26-specific tips

N26 likes when you note that JavaScript's Map preserves insertion order, which gives you a clean O(1) LRU without hand-rolling a linked list - the same shortcut they use in their balance-cache prototype.

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

Practice these live with InterviewChamp.AI →