LRU Cache
A fixed-capacity cache with O(1) get/put and least-recently-used eviction.
Easy30 minHash map + DLLEviction policyThread safety
Design a Least Recently Used (LRU) cache with fixed capacity and O(1) get and put. It's a classic because it mixes data-structure knowledge (hash map plus doubly linked list) with design concerns like pluggable eviction and thread safety.
Requirements
Functional
get(key)returns the value or a miss indicator, and marks the key as most recently used.put(key, value)inserts or updates; if capacity is exceeded, evict the least recently used entry.- Fixed capacity set at construction.
- Optional: TTL per entry, eviction callback, hit/miss stats, pluggable eviction policy (LFU, FIFO).
Non-functional
- O(1) average time for
getandput. - Thread-safe for concurrent readers and writers.
- Generic over key and value types.
Try it first
Set a timer, sketch your own design on paper, then compare it with the reference walkthrough.
30:00
Defend it out loud
The AI interviewer will probe your design for LRU Cache and score it.