Add TTL to an LRU cache
Company: ByteDance
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: hard
Interview Round: Onsite
Design an in-memory LRU cache and explain how to extend it with TTL support.
Requirements:
- `get(key)` returns the value if the key exists and has not expired; otherwise it returns a cache miss.
- `put(key, value, ttl)` inserts or updates an entry with an expiration time.
- When capacity is exceeded, evict the least recently used item.
- Expired items should never be returned, and the design should explain how they are removed.
- Discuss the data structures, time complexity, cleanup strategy, and concurrency considerations.
Overview: This question evaluates a candidate's understanding of cache design, LRU eviction policies, time-to-live (TTL) semantics, appropriate data structures, time complexity reasoning, and concurrency control.