Implement a Map with Time Expiration
Design a map that supports standard `put` and `get` operations, but each key-value pair automatically expires after a given Time-To-Live (TTL).
Why Interviewers Ask This
Uber interviewers ask this to evaluate your ability to balance time complexity with real-world concurrency and memory management. They specifically test if you can design a system that handles automatic cleanup without blocking the main thread, a critical requirement for high-throughput ride-hailing services where stale location data must be discarded instantly.
How to Answer This Question
1. Clarify requirements immediately: define TTL units (milliseconds vs seconds) and whether operations are synchronous or asynchronous.
2. Propose a hybrid data structure: Combine a Hash Map for O(1) access with a Min-Heap (Priority Queue) to track expiration times efficiently.
3. Discuss the eviction strategy: Explain lazy deletion during 'get' operations versus background threads for proactive cleanup, noting trade-offs in latency.
4. Address concurrency: Mention thread safety mechanisms like locks or atomic operations, as Uber systems handle massive parallel requests.
5. Optimize space complexity: Suggest removing entries from the heap only when necessary to avoid O(N) scanning costs on every insertion.
Key Points to Cover
- Demonstrating understanding of Lazy vs Eager deletion strategies
- Selecting the correct combination of Hash Map and Priority Queue
- Addressing Thread Safety and Concurrency in high-load scenarios
- Analyzing Time Complexity for both Put and Get operations
- Considering Memory Management implications of unbounded growth
Sample Answer
To implement a Map with Time-To-Live, I would combine a HashMap for fast key lookups with a Min-Heap to manage expiration order. First, we store each entry as an object containing the value, the insertion timestamp, and…
Common Mistakes to Avoid
- Ignoring concurrency issues by assuming single-threaded execution
- Scanning the entire data structure on every get to find expired items
- Failing to define how the expiration timestamp is calculated relative to clock skew
- Overlooking the memory overhead of storing timestamps alongside values
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.