LRU Cache With TTL

Problem Implement an LRU cache where each entry also carries a time-to-live (TTL); expired entries are treated as absent.

Requirements

• get(key) returns the value if present and not expired, else a miss; a hit counts as a use (most-recently-used).
• put(key, value, ttl) inserts/updates and, when over capacity, evicts the least-recently-used entry.
• Both operations should be O(1).

Areas to design

• The data structures giving O(1) lookup plus O(1) recency reordering.
• How and when TTL expiry is enforced (lazy on access vs active sweeping).
• Concurrency (optional follow-up): making get/put thread-safe.

Example

• put(a,1,ttl=5); after ttl elapses, get(a) → miss even though capacity was never exceeded.