Design an In-Memory Key-Value Cache

Problem Statement

Design and implement a robust, in-memory key-value cache with capacity limits, LRU (Least Recently Used) eviction, and optional per-key TTL (Time-To-Live) expiration. Your implementation must be safe for concurrent use by multiple threads.

Class Interface

from typing import Any, Optional

class KeyValueStore:
    def __init__(self, capacity: int):
        """
        Initialize the store with a maximum capacity of live entries.
        """
        pass

    def get(self, key: str) -> Optional[Any]:
        """
        Retrieve the value for key if present and not expired.
        Updates the recency of the key.
        Returns None if key is absent or expired.
        """
        pass

    def put(self, key: str, value: Any, ttl: Optional[float] = None) -> None:
        """
        Insert or update a key-value pair with an optional TTL (in seconds).
        If key exists, updates its value, TTL, and recency.
        If at capacity, evicts expired items first; if still at capacity,
        evicts the least recently used live item.
        """
        pass

    def delete(self, key: str) -> bool:
        """
        Explicitly remove a key. Returns True if removed, False otherwise.
        """
        pass

    def size(self) -> int:
        """
        Returns the count of valid (non-expired) items currently stored.
        """
        pass

Requirements & Semantics

1. Complexity: get, put, and delete should run in O(1) average time.
2. Eviction Order: When at capacity during a put:
   • Check and remove expired entries first if possible.
   • If the cache remains at capacity, evict the least recently used (LRU) entry.
3. TTL Handling: A key with a TTL expires after current_time + ttl. Expired entries must never be returned by get.
4. Concurrency: All operations must be thread-safe.

Example

cache = KeyValueStore(capacity=2)

cache.put("a", 1, ttl=10.0)
cache.put("b", 2, ttl=10.0)
assert cache.get("a") == 1       # "a" is now most recently used
cache.put("c", 3)                # Capacity full; "b" is LRU -> evicts "b"
assert cache.get("b") is None
assert cache.get("c") == 3

Constraints & Edge Cases

• capacity >= 1
• ttl is either None (no expiration) or a positive float (ttl > 0).
• Handle cases where an entry expires before being accessed or updated.
• Avoid deadlocks during concurrent access.