Design an Extensible Cache (LRU / LFU Eviction)
In a 45-minute LLD interview, the key challenge is separation of concerns: cleanly decoupling raw key-value storage (Cache<K, V>) from the key eviction sequence (EvictionPolicy<K>). The interviewer expects strict O(1) average time complexity for get, put, and eviction. Scope the solution to generic key-value types, capacity enforcement, LRU eviction using a doubly-linked list + hash map, and a swappable FIFO policy. Mention C++23 std::flat_map trade-offs, thread-safe sharded caches, and TTL expiration as extensions.
Problem statement & clarifying requirements
Design an extensible, in-memory generic cache Cache<K, V> that supports fast lookups, insertions, updates, and removals with configurable capacity. The cache must cleanly separate value storage from eviction order so that different eviction algorithms (Least Recently Used (LRU), First-In First-Out (FIFO), and future algorithms like LFU) can be swapped in without modifying the core cache storage logic.
All core operations (get, put, and eviction) must run in O(1) average time.
The value is overwritten, the cache size does not increase, and the key is marked as most recently accessed in the eviction policy.
No. A cache miss returns an empty optional (std::nullopt) and does not modify the eviction policy order.
A zero-capacity cache rejects all insertions without error. Evicting from an empty policy safely returns std::nullopt.
First, sketch the design yourself
Spend 5 minutes listing the classes, who owns whom, and which interface hides the part that changes.
- 1.
Decouple storage from eviction order: If the hash map holds list iterators directly and the eviction logic is hardcoded inside
Cache, switching to FIFO or LFU requires rewriting the entire cache class. - 2.
Use a doubly-linked list combined with a hash table: A linked list gives O(1) node removal and head/tail splicing, while a hash map maps keys to list node iterators for O(1) lookup.
- 3.
Maintain ownership boundaries:
Cache<K, V>owns the eviction policy viastd::unique_ptr<EvictionPolicy<K>>, while the policy only tracks keys (K), never values (V).
How to think through this problem (5-step walkthrough)
In a 45-minute LLD interview, the key challenge is separation of concerns: cleanly decoupling raw key-value storage (Cache<K, V>) from the key eviction sequence (EvictionPolicy<K>). The interviewer expects strict O(1) average time complexity for get, put, and eviction. Scope the solution to generic key-value types, capacity enforcement, LRU eviction using a doubly-linked list + hash map, and a swappable FIFO policy. Mention C++23 std::flat_map trade-offs, thread-safe sharded caches, and TTL expiration as extensions.
Not every noun in the prompt deserves its own class. Separate dumb data structs from stateful managers, and turn trivial nouns into fields or enums.
Cache<K, V>Generic context managing value storage (std::unordered_map<K, V>), capacity bounds, and delegating eviction notifications to the injected policy.
EvictionPolicy<K>Strategy interface tracking key access order (keyAccessed), selecting victim keys (evictKey), and updating on explicit removal (keyRemoved). Tracks keys only, never values.
LruEvictionPolicy<K>Implements O(1) LRU policy using a doubly-linked list (std::list<K>) and an iterator hash map (std::unordered_map<K, std::list<K>::iterator>).
FifoEvictionPolicy<K>Implements First-In First-Out eviction, appending only newly inserted keys to arrival order without repositioning on cache reads.
CacheHitCounter / TimestampEntryTrap noun — beginners often introduce TimestampEntry (storing epoch timestamps to sort for LRU, taking O(N) or O(log N) heap time) or CacheHitCounter as standalone classes. LRU requires access ordering, not wall-clock timestamps; and hit/miss metrics are simply integer member counters on Cache.
A beginner embeds a doubly-linked list directly inside the Cache class, storing both keys and values in list nodes. When asked to switch to FIFO or LFU eviction, or to benchmark eviction strategies under different workloads, the entire cache implementation must be duplicated or rewritten. Alternatively, beginners store timestamps on entries and perform O(N) scans to find the oldest entry, failing the O(1) performance requirement.
Hardcoding list node splicing directly inside Cache<K, V> tightly couples storage to a single eviction heuristic and forces code duplication for alternative policies.
Passing values into the eviction policy bloats memory and prevents reusing the policy for key-only sets or metadata indexes.
- ✓
O(1) Access and Splicing invariant:
LruEvictionPolicymaintainsnodeMap_pointing directly to list nodes, ensuringkeyAccessedrelocates the node to the front viastd::list::splicein O(1) time without memory reallocation. - ✓
Capacity and Synchronization invariant:
storage_.size()must never exceedcapacity_. When inserting a new key at capacity,policy_->evictKey()must return an existing key, which is erased fromstorage_before the new entry is inserted. - ✓
Ownership invariant:
Cache<K, V>exclusively ownsstd::unique_ptr<EvictionPolicy<K>>. The policy maintains key identity order but holds no pointers or references toV.
Entities & design patterns used
Unlock Full UML Diagram & C++23 Solution
The complete UML diagram, production-ready C++23 code, follow-up extensions, and design pitfall analysis are part of Brute2Best Pro. All 7 foundation chapters are 100% free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.