Algorithm selectionIntermediate
Bounded cache with eviction
Scenario
A service caches responses keyed by request id. Memory allows at most capacity entries. When full, evict the entry that has not been used for the longest time. Both get and put must be O(1). Choose the data structures and explain why simpler options fail.
Your task
- Clarify: does
getcount as "use"? Doesputon an existing key update recency? What happens oncapacity = 0? - Try a single hash map with timestamps; explain why eviction is not
O(1). - Try a hash map plus a heap of timestamps; explain why refreshing recency is not
O(1). - Present the structure that achieves
O(1)for everything and state the invariants linking its two parts. - Name the Python shortcut and say what it hides.
Pattern RecognitionImplementationProblem Clarification
Work it out
Write your analysis before revealing anything. The self-check below compares it against what a strong answer contains.
Reveal
Progressive — each section builds on the previous one.
Key observation
The fix
Edge cases
Complexity
What this tests
Self-check
Tick what your analysis covered. Be honest — this feeds your readiness profile.