Cache with TTL and Capacity

Design and implement an in-memory key-value cache that supports TTL-based expiration and has a fixed capacity. When the cache is at capacity and a new key is inserted, the least recently used (LRU) entry should be evicted. Each entry has a value and an expiration time (TTL). On a get(key) operation, return the value only if the entry exists and has not expired; otherwise return null. On a set(key, value, ttl) operation, store the entry with the given TTL (in milliseconds). If the cache is at capacity, first evict any expired entries; if still at capacity, evict the LRU entry before inserting the new one. All operations must be O(1) average time.