LRU Cache with TTL Expiration

Problem: Implement an LRU Cache with TTL Expiration Design and implement LRUCacheTTL, which extends a standard LRU cache by adding TTL (time-to-live) expiration. The cache should support the following operations (aim for amortized O(1)): put(key, value, ttl): Insert/update a key with a TTL provided as an additional parameter on each call. If key exists: update value and the expiration for that key, and mark it as most recently used. If key does not exist: insert it. If capacity is exceeded: evict the least recently used non-expired entry. get(key): Retrieve the value for key. If the key does not exist or is expired: return a miss (e.g., -1/null) and ensure the key is treated as absent (delete it). If present and not expired: return value and mark it as most recently used. Expiration semantics Each entry has an expiration time derived from its TTL at write time. Once expired, the entry must be treated as nonexistent even if it still appears in the LRU structure. Whenever an operation (get or put) discovers an entry is expired, it should be removed. Interface (suggested) LRUCacheTTL(capacity) get(key) -> value or -1 put(key, value, ttl) -> void Constraints / Requirements capacity > 0 key is hashable (int/string) Explain time complexity; implement LRU via hash map + doubly linked list and incorporate TTL-based deletion. Example Input # capacity=2 put(1, 10, ttl=100) get(1) Output 10