LRU Cache With TTL

Problem Implement an LRU (least-recently-used) cache where each entry also carries a time-to-live (TTL). get and put must run in O(1); an entry that has outlived its TTL must behave as absent, and when the cache is full the least-recently-used live entry is evicted to make room.

Requirements

• get(key) -> value or miss; refreshes recency.
• put(key, value, ttl) -> inserts or updates, may evict.

Areas to design

• The data structures giving O(1) lookup and O(1) recency updates.
• When expired entries are detected and reclaimed (lazy on access vs active sweep).
• Making the cache safe under concurrent access.

Example

• put(a, 1, ttl=100); get(a) hits; once the TTL elapses, get(a) misses even before the entry is evicted.