Implement an LRU Cache with TTL Expiration
Last updated: September 4, 2025
Quick Overview
Build an LRU cache with per-key time-to-live. Tests doubly-linked list, hashmap, and heap for expiration management.
Perplexity
September 4, 20258
6
4,208 solved
Build an LRU cache with per-key time-to-live. Tests doubly-linked list, hashmap, and heap for expiration management.
Common at search companies for query caching. At Perplexity, this relates directly to caching LLM responses and search results.
What the Interviewer Expects
- Implement O(1) get and put operations
- Add TTL-based expiration per key
- Handle lazy versus eager expiration strategies
- Use doubly-linked list and hashmap
- Discuss the trade-off between memory and eviction precision
Key Topics to Cover
How to Approach This
- Clarify input constraints and edge cases before writing code.
- Walk through your approach verbally and confirm with the interviewer before coding.
- Start with a brute force solution, then optimize. Mention time and space complexity.
- Test your solution with examples, including edge cases like empty input or duplicates.
- Consider common patterns: sliding window, two pointers, hash map, BFS/DFS, dynamic programming.
Possible Follow-up Questions
- How would you handle TTL in a distributed cache?
- What eviction policy would you use when both TTL and capacity limits apply?
- How would you add probabilistic early expiration to prevent thundering herd?
Sharpen Your Skills on Codemia
Practice similar problems with our interactive workspace, get AI feedback, and track your progress.
Practice DSA ProblemsSample Answer
Core Implementation
Combine a standard LRU (doubly-linked list + hashmap) with per-key timestamps. On get(), check if the key has expired before returning. On put(), set ...
Expiration Strategy
Lazy expiration: on every get(), check if expires_at < now. If expired, treat as cache miss and remove the entry. This avoids the overhead of a backgr...
Submit Your Answer
