Implement Expiring LRU Cache

Implement an in-memory key-value cache with least-recently-used eviction and per-entry expiration.

The cache has a fixed positive capacity. Each inserted key has a time-to-live value. Once an entry expires, it should behave as if it does not exist and should be removed from the cache when encountered.

Design a class with the following operations:

ExpiringCache(int capacity)
int get(int key, int now)
void put(int key, int value, int ttl, int now)

Rules:

• put(key, value, ttl, now) inserts or updates key with value.
• The entry expires at time now + ttl.
• get(key, now) returns the value if the key exists and has not expired; otherwise return -1.
• Accessing a non-expired key through get makes it the most recently used entry.
• Updating an existing non-expired key through put updates its value, expiration time, and recency.
• If an existing key has already expired, treat the operation as inserting a new key.
• If inserting a new entry causes the number of non-expired entries to exceed capacity, evict the least recently used non-expired entry.
• Expired entries should be deleted when detected.

Target: make get and put run in O(1) average time, using an appropriate combination of a hash map and a doubly linked list.

Implement Expiring LRU Cache

Design an in-memory key-value cache with both least-recently-used eviction and per-entry expiration.

A normal LRU cache tracks recency of use. This version also gives every key a time-to-live (TTL). If a key was inserted or updated at time now with TTL ttl, then it expires at time now + ttl and is valid only while current_time < now + ttl.

For this challenge, implement a function solution(capacity, operations) that simulates the cache and returns the results of all get operations.

Each operation is one of:

• ('put', key, value, ttl, now)
• ('get', key, now)

Cache rules:

• put(key, value, ttl, now) inserts or updates key with value.
• The key expires at time now + ttl.
• get(key, now) returns the value if the key exists and has not expired; otherwise return -1.
• Accessing a non-expired key through get makes it the most recently used entry.
• Updating an existing non-expired key through put updates its value, expiration time, and recency.
• If an existing key has already expired, treat the put as inserting a new key.
• If inserting a new non-expired entry causes the number of non-expired entries to exceed capacity, evict the least recently used non-expired entry.
• Expired entries should behave as if they do not exist and should be deleted when detected.

Assume operation timestamps are non-decreasing.

Constraints

• 1 <= capacity <= 10^5
• 1 <= len(operations) <= 2 * 10^5
• 0 <= key, value, now <= 10^9
• 1 <= ttl <= 10^9
• The now values in operations are non-decreasing

Examples

Example 1

Input: (2, [('put', 1, 10, 5, 0), ('put', 2, 20, 5, 1), ('get', 1, 2), ('put', 3, 30, 5, 3), ('get', 2, 4), ('get', 1, 5), ('get', 3, 7)])
Output: [10, -1, -1, 30]

Explanation: Key 1 is read before it expires, making it most recently used. Inserting key 3 evicts key 2 as the LRU non-expired key. At time 5, key 1 expires exactly then, so it returns -1.

Example 2

Input: (2, [('put', 1, 100, 2, 0), ('put', 1, 111, 5, 1), ('get', 1, 2), ('put', 2, 200, 10, 2), ('put', 1, 123, 1, 6), ('get', 1, 6), ('get', 2, 6), ('get', 1, 7)])
Output: [111, 123, 200, -1]

Explanation: The first update to key 1 happens before expiration, so it refreshes value and TTL. At time 6, the old key 1 has already expired, so that put acts like a fresh insertion. At time 7, the new version expires exactly then.

Hints

1. For the LRU behavior, the standard approach is a hash map for O(1) key lookup plus a doubly linked list for O(1) recency updates.
2. Expiration can happen even for keys you do not directly access. Consider an additional structure ordered by expiration time and use lazy deletion to discard stale records.