Prompt and context
Implement a bounded LRU-K cache supporting get, put, and eviction. Keep the most recent K accesses per key. Entries with fewer than K accesses form a history-incomplete tier and must be evicted before hot entries. Clarify K, capacity, updates to existing keys, concurrent calls, and missing keys.
What the interviewer is testing
- Whether you maintain access history and the two candidate tiers correctly.
- Whether you can choose a heap, hash map, or ordered structure and analyze cost.
- Whether you handle overwrites, zero capacity, invalid K, and concurrent visibility.
- Whether you understand that LRU-K filters scan pollution rather than winning on every workload.
Clarifying questions before answering
Confirm thread safety, approximate eviction, mutable values, TTL requirements, and hit-rate metrics. Strict ordering usually needs a lock or serialized updates; higher throughput may require sharding and an approximate policy.
30-second answer framework
Store the value, the latest K logical timestamps, and a version per key. Split candidates into history-incomplete and hot tiers. When over capacity, evict the oldest item in the incomplete tier; otherwise evict the hot item with the smallest K-th most recent timestamp. A hash map gives O(1) lookup and heaps maintain candidates; versions discard stale heap nodes. Strict get and put are expected O(log n), with O(capacity·K) history space.
Step-by-step deep dive
1. Recording access history
Append a logical clock value on every hit or write and retain only the latest K values. A logical clock compares order without wall-clock jumps and distinguishes accesses in the same millisecond. An overwrite counts as an access unless the prompt says writes do not count.
2. Maintaining eviction candidates
The incomplete tier is ordered by its latest access; the hot tier by its K-th most recent access. Keep two min-heaps of (key, version, rank). A new access pushes a new node and increments the version; eviction validates version and current rank, skipping stale nodes.
3. Boundaries and concurrency
Do not cache when capacity is zero or negative; reject K when it is zero or negative. Eviction and value updates must share a critical section so concurrent put calls cannot exceed capacity. Sharded locks improve throughput, but global capacity then needs coordination.
High-quality sample answer
I separate entries into history-incomplete and hot tiers. Each entry stores its value, latest K logical times, and version; an access updates history and pushes a new rank node into the relevant min-heap. Eviction checks the incomplete heap first, then the hot heap, validating versions to skip stale nodes. Lookup is O(1) through the map, heap work is O(log n), and history space is O(capacity·K). Tests cover K=1 behaving like LRU, promotion after repeated access, one-time scans, overwrites, zero capacity, concurrent over-capacity writes, stale heap nodes, and hit rate. LRU-K targets scan pollution; Redis uses sampled LRU approximations and PostgreSQL uses clock-sweep, so their cost and behavior should not be conflated.
Common mistakes
- Keeping one timestamp and accidentally implementing ordinary LRU.
- Treating the latest access as the K-th most recent access.
- Removing a heap root without handling duplicate stale nodes.
- Letting concurrent
putcalls exceed capacity or updating history outside the lock. - Claiming LRU-K always beats LRU.
Follow-up questions and responses
What should happen when K equals 1?
The first access gives an entry hot semantics, so eviction is ordered by its latest access and the policy reduces to ordinary LRU ordering.
How can you reduce heap-node memory?
Use indexes and a mutable heap to reduce duplicate nodes, or choose generational queues or sampled eviction. State that ordering becomes approximate and remeasure hit rate.
How would you measure reduced scan pollution?
Create a cyclic hot set, then insert many keys accessed once. Compare LRU and LRU-K on hot-set hit rate, evictions, latency, and memory, including a hot set close to capacity.