Time-Aware LRU Cache

Cache Design Lru

Design and implement a time-aware Least Recently Used (LRU) Cache. Your cache should support the following operations:

  1. set(key, value, ttl):

    • Insert the key-value pair along with a time-to-live (TTL) parameter (in seconds).
    • If the cache reaches its maximum capacity, evict the least recently used (non-expired) item to make room for the new entry. Expired items should be removed or ignored upon access.

  2. get(key):

    • If the key exists and has not expired, return its value and update its usage to mark it as recently accessed.
    • If the key does not exist or if it has expired, return null (or an equivalent value in your chosen language).

Requirements:

  • The cache should have a configurable maximum capacity defined at initialization.
  • All operations (get and set) should be efficient, ideally with O(1) time complexity on average.
  • The TTL for each key indicates the duration (in seconds) for which the key remains valid after insertion. Use appropriate time tracking to determine expiration.
  • Expired keys should be treated as if they do not exist when accessed, even if they are still lingering in the cache data structure.

Task:

Implement this time-aware LRU Cache in your preferred programming language. Include a simple test suite that demonstrates the correct behavior of your cache.