Simulate a TTL Cache with LRU Eviction

Problem Statement

Design a fixed-capacity key-value cache that supports per-key time-to-live (TTL) expiration alongside Least Recently Used (LRU) eviction. All operations receive an explicit non-decreasing integer timestamp.

Implement the TTLCache class:

• TTLCache(capacity: int): Initializes the cache with a positive integer capacity.
• get(timestamp: int, key: str) -> int: Returns the value of key if it exists and has not expired (timestamp = expiration_time), return -1. Accessing a live key marks it as the most recently used. If the key is expired, it must be removed from the cache.
• set(timestamp: int, key: str, value: int, ttl: int) -> None: Stores or updates key with value and sets its expiration time to timestamp + ttl.
  • If key already exists (even if previously expired), update its value and expiration, and mark it as most recently used.
  • If key does not exist and the cache is at capacity, evict the least recently used key before inserting the new entry.
  • Mark the newly inserted entry as the most recently used.

Both get and set must run in O(1) average time without scanning the entire cache.

Interface

class TTLCache:
    def __init__(self, capacity: int):
        pass

    def get(self, timestamp: int, key: str) -> int:
        pass

    def set(self, timestamp: int, key: str, value: int, ttl: int) -> None:
        pass

Examples

Example 1

cache = TTLCache(2)

cache.set(1, "a", 10, 5)   # "a" stored with value 10, expires at 1 + 5 = 6
cache.set(2, "b", 20, 10)  # "b" stored with value 20, expires at 2 + 10 = 12

cache.get(3, "a")          # returns 10 (3 < 6; "a" is now most recently used)
cache.set(4, "c", 30, 5)   # cache is full; evicts LRU key "b"; stores "c" (expires at 9)

cache.get(7, "a")          # returns -1 ("a" expired at 6; removed from cache)
cache.get(7, "b")          # returns -1 ("b" was evicted at t=4)
cache.get(7, "c")          # returns 30 (7 < 9; "c" is valid)

Example 2

cache = TTLCache(1)

cache.set(0, "k", 100, 10) # "k" expires at 10
cache.get(10, "k")         # returns -1 (expired at 10, removed)
cache.set(11, "k", 200, 5) # re-inserted as new key, size is 1/1
cache.get(12, "k")         # returns 200

Constraints

• 1 <= capacity <= 10^5
• 0 <= timestamp <= 10^9
• 1 <= ttl <= 10^6
• 1 <= len(key) <= 30 (alphanumeric strings)
• 0 <= value <= 10^9
• Timestamps across consecutive calls are non-decreasing (timestamp_{i} <= timestamp_{i+1}).
• Up to 2 * 10^5 total calls to get and set.