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
Coding & Algorithms
Software Engineer
Perplexity
September 4, 2025Software Engineer
Coding Round
Coding & Algorithms
Medium
8
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
LRU cache
TTL expiration
Doubly-linked list
HashMap
Cache eviction
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
Problem Analysis
This problem requires implementing an LRU (Least Recently Used) Cache with an additional feature of per-key TTL (Time-To-Live) expiration. The LRU caching mechanism ensures that we maintain a limit on...
Approach
- Data Structures:
- Use a hashmap (
cache) to map keys to their corresponding nodes in the doubly-linked list. - Each node will contain the key, value, and a timestamp indicating when i...
- Use a hashmap (
Submit Your Answer
Markdown supported