Implement an LRU Cache with TTL Support
Last updated: April 5, 2025
Quick Overview
Build a Least Recently Used cache that supports time-to-live expiration on entries, with O(1) get and put operations and lazy expiration cleanup.
Canva
April 5, 202510
5
3,876 solved
Build a Least Recently Used cache that supports time-to-live expiration on entries, with O(1) get and put operations and lazy expiration cleanup.
Caching is essential at Canva's scale for reducing latency on template rendering, asset delivery, and permission checks. This question tests your ability to combine two classic data structure concepts (LRU eviction and TTL expiration) into a clean, performant implementation.
What the Interviewer Expects
- Implement O(1) get and put using a hash map and doubly linked list
- Add TTL support with lazy expiration on access
- Handle capacity-based eviction when the cache is full
- Write clean, production-quality code with proper error handling
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 add active cleanup of expired entries without blocking reads?
- How would you make this thread-safe for concurrent access?
- How would you instrument this cache with hit rate metrics?
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
The problem requires us to implement an LRU (Least Recently Used) cache that also supports TTL (time-to-live) for its entries. Given that both LRU eviction policy and TTL expiration are classic proble...
Approach
- Data Structures: Use a hash map (
cache) to store key-value pairs, where the value is a node in a doubly linked list. Each node holds the key, value, and timestamp of when it was last accessed...
Submit Your Answer
