Design an Expiring LRU Cache | Dataford Interview Questions

Implement a cache that supports get(key) and put(key, value, ttl) in O(1) average time. The cache has a fixed capacity. When the capacity is full, evict the least recently used unexpired entry first. Each entry also expires ttl seconds after insertion; expired entries must not be returned and should be removed lazily during normal operations.

Return -1 from get(key) if the key is missing or expired. Assume a monotonic integer current_time is provided to each operation in non-decreasing order.

Constraints

1 <= capacity <= 10^5
1 <= number of operations <= 10^5
1 <= key <= 10^9
-10^9 <= value <= 10^9
1 <= ttl <= 10^9
current_time is non-decreasing across operations
get and put must run in average O(1) time

Function Signature

def process_cache_operations(capacity, operations):

Your question is Design an Expiring LRU Cache. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Return -1 from get(key) if the key is missing or expired. Assume a monotonic integer current_time is provided to each operation in non-decreasing order.

Constraints

1 <= capacity <= 10^5
1 <= number of operations <= 10^5
1 <= key <= 10^9
-10^9 <= value <= 10^9
1 <= ttl <= 10^9
current_time is non-decreasing across operations
get and put must run in average O(1) time

Function Signature

def process_cache_operations(capacity, operations):

Your question is Design an Expiring LRU Cache. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.