Stage 3: LRU Cache with TTL

Objective:Layer per-entry TTL expiry on top of the LRU eviction policy, and understand how lazy expiry interacts with capacity tracking.

The LRU cache with TTL stores an expiresAt timestamp alongside each cached value. On get: check if currentTime >= expiresAt -- if so, evict the entry and return -1 (as if it were never there). On put: compute expiresAt = currentTime + ttl where ttl defaults to defaultTTL.

Lazy expiry means you only check expiry when a key is accessed. A key might be "expired" in the sense that its TTL has passed but still physically present in the cache -- it will be evicted on the next access. This is the Redis behavior for keys without a background eviction sweep.

Expired entries and capacity: Expired entries do NOT count toward capacity for eviction purposes. If the cache is at capacity and all existing entries are expired, no live entry should be evicted. Implement this by checking expiry before deciding to evict the LRU tail.

Implement createLRUCacheWithTTL(capacity, defaultTTL) returning:

• get(key, currentTime) -- return value if present and not expired, else -1; evict on expiry
• put(key, value, currentTime, ttl?) -- store with expiresAt = currentTime + (ttl ?? defaultTTL); if over capacity after adding live entries, evict the LRU non-expired tail
• size -- number of entries in the cache (including potentially expired ones not yet lazily evicted)

Why this matters in production

Every production cache combines eviction (LRU -- what to drop when full) with expiry (TTL -- what to drop when stale). Redis's EXPIRE command, HTTP Cache-Control max-age, and DNS TTL fields are all the same concept: each entry has an absolute time after which it is invalid. The interesting design question is when to actually remove expired entries -- eagerly (background sweep) or lazily (on access). Redis does both: lazy expiry on get, plus a background thread that periodically samples and evicts expired keys. This stage implements lazy expiry, which is simpler, correct, and what most embedded caches use.