Implement an LFU / TTL Cache

Problem Implement a cache supporting get(key) and put(key, value) in O(1) average time, with a capacity limit that triggers eviction and a per-key time-to-live (TTL) after which an entry is treated as absent.

Input / Output

• Input: a sequence of get(key) and put(key, value, ttl) operations plus a fixed capacity.
• Output: get returns the value if present and not expired, else a miss; put inserts/updates and evicts if over capacity.

Constraints

• All operations should be average O(1) despite a high request rate.
• On overflow evict per the chosen policy — LFU (least-frequently-used) or LRU (least-recently-used).
• An entry past its TTL must never be returned, even before it is physically evicted.

Example

• Capacity 2: put(a), put(b), get(a) (hit), put(c) evicts the least-valued of {a,b} per policy; a key inserted with a short TTL returns a miss once its TTL elapses.