Time-Bound LRU Cache

Data Structures System Design Cache

You are tasked with designing and implementing a data structure that functions as a Least Recently Used (LRU) cache with an additional twist: each key-value pair inserted into the cache has a specified Time-To-Live (TTL).

Requirements:

  1. Cache Capacity: The cache has a maximum capacity. Once the cache is full, the least recently used item should be evicted before inserting a new item.

  2. TTL for Keys: Each key inserted in the cache should have an associated TTL (in seconds, milliseconds, or any given unit). A key should automatically be treated as expired and removed if its TTL has passed (i.e., the current time exceeds the inserted time plus TTL).

  3. Operations:

    • get(key): Retrieve the value of the key if it exists and is not expired, and mark it as recently used. If the key is not present or is expired, return an appropriate indicator (like -1 or null).
    • put(key, value, ttl): Insert or update the key with its value and TTL. If updating an existing key, refresh its TTL and mark it as recently used. If the cache is at capacity, evict the least recently used item that is not fresh before inserting the new key-value pair.

  4. Time Management: Assume you have access to a function that provides the current time in your language of choice. Use this to determine if a key is expired whenever get or put operations are invoked.

  5. Efficiency: Aim for O(1) time complexity for both get and put operations under normal and edge conditions.

Additional Considerations:

  • Consider how the system should behave during the cleanup of expired keys. Should it be handled lazily (only when operations occur) or actively (a background process)?

  • Ensure that your design handles edge cases, such as simultaneous expirations or updating keys that are already expired.

Provide a complete implementation in your preferred programming language along with sample test cases that demonstrate the correctness of your design.