9. LRU Cache

mediumAsked at Confluent

Design an O(1) get/put cache with least-recently-used eviction — Confluent uses it because the same doubly-linked-list + map idea powers consumer-side caches sitting in front of partition reads.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

Design a data structure that follows LRU semantics with O(1) get and put. On capacity overflow evict the least recently used key. get and put both count as usage.

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); get(1); put(3,3)

Output

evicts key 2

Approaches

1. Map plus sort by timestamp

Store entries with a timestamp; on eviction scan for the oldest.

Time: O(n) per put
Space: O(n)

// store {k: {v, ts}}; on full, scan all entries for min ts and delete

Tradeoff:

2. Map plus doubly linked list

Map keys to nodes in a DLL ordered by recency; move on access, drop from tail on eviction. All operations are O(1).

Time: O(1) per op
Space: O(n)

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

Tradeoff:

Confluent-specific tips

Confluent grades LRU answers on whether you can extend the cache to be partition-aware — call out that exactly-once semantics require evictions be reflected in a state-store changelog so they survive consumer-group rebalance.

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

Practice these live with InterviewChamp.AI →