Auto-Expire Cache

Problem Overview

Design and implement a key-value cache with automatic expiration. The system should allow storing key-value pairs that automatically expire after a specified duration.

This is similar to LeetCode 2622 - Cache With Time Limit.

You'll build this incrementally across multiple parts, with each part extending the previous functionality.

Key Design Considerations

1. API Design: Consider what the interface should look like, what types the inputs/outputs should be, and edge cases.
2. Expiration Strategy: How and when do expired entries get removed?
3. Memory Efficiency: How do you prevent memory leaks from expired but not-yet-removed entries?
4. Thread Safety: Consider how concurrent access would work in a distributed system.

Also Known As: Log Rate Limiter

This problem is frequently asked at Netflix under the name "Log Rate Limiter" with a slightly different framing:

Given a time window (e.g., 1 minute), implement a print function that takes an event with name and timestamp. If the same event name was seen within the time window, suppress it; otherwise, print it.

Interview flow typically follows:

1. Start with the basic solution using a map to store seen events and their timestamps
2. Discuss memory issues if the rate limiter runs for a long time or handles massive data
3. Discuss deletion strategies: LRU, lazy deletion, or periodic cleanup (cron job)
4. Follow-up: How would you handle out-of-order timestamps while maintaining LRU?

---

Part 1: Basic Auto-Expire Cache

Problem Statement

Implement an AutoExpireCache class with the following methods:

class AutoExpireCache:
    def __init__(self):
        """Initialize the cache."""
        pass
    
    def set(self, key: str, value: Any, ttl_seconds: int) -> None:
        """
        Store a key-value pair that expires after ttl_seconds.
        
        Args:
            key: The cache key
            value: The value to store (can be any type, including False/None/0)
            ttl_seconds: Time-to-live in seconds
            
        Notes:
            - If key already exists, override it with new value and TTL
            - TTL countdown starts from the moment set() is called
        """
        pass
    
    def get(self, key: str) -> Any:
        """
        Retrieve a value by key.
        
        Args:
            key: The cache key
            
        Returns:
            The value if key exists and hasn't expired, None otherwise
            
        Notes:
            - Return None for expired keys (not False, as False can be a valid value)
            - This is a good time to clean up the expired entry (lazy deletion)
        """
        pass

API Design Discussion Points

During the interview, be prepared to discuss:

1. Return value for cache miss: Why return None instead of False?

   • False can be a valid cached value
   • Could also raise an exception, but None is more Pythonic for "not found"

2. Should set return anything?

   • Could return True/False for success
   • Could return the previous value if key existed
   • Keeping it simple (void) is usually fine

3. Error handling: Should we validate inputs?

   • Negative TTL?
   • Empty key?
   • For this interview, simple validation is sufficient

Example Usage

import time

cache = AutoExpireCache()

# Set a value with 2 second TTL
cache.set("user_session", {"user_id": 123}, 2)

# Immediately get - should return the value
print(cache.get("user_session"))  # {"user_id": 123}

# Wait for expiration
time.sleep(3)

# After expiration - should return None
print(cache.get("user_session"))  # None

# Test with False as a valid value
cache.set("feature_flag", False, 60)
result = cache.get("feature_flag")
print(result)            # False
print(result is None)    # False (it's actually the value False, not None)

---

Part 2: Preventing Memory Leaks

Problem Statement

Interviewer: "Your current implementation has a memory issue. If we set millions of keys that are never accessed again, they'll stay in memory forever even after expiring. How would you handle this?"

Discuss and implement strategies to actively clean up expired entries.

Part 3: Fixed-Size LRU Cache with Expiration

Problem Statement

Interviewer: "What if memory is still a concern and we need to enforce a maximum cache size? Implement a bounded cache that evicts the least recently used entries when full."

Modify the cache to have a fixed capacity and use LRU eviction:

class AutoExpireCache:
    def __init__(self, capacity: int):
        """
        Initialize a bounded cache with LRU eviction.
        
        Args:
            capacity: Maximum number of entries the cache can hold
        """
        pass

Requirements

1. Fixed capacity: Never exceed the specified number of entries
2. LRU eviction: When full, evict the least recently used entry
3. Expiration still works: Expired entries should still be treated as non-existent
4. Access updates recency: Both get and set should update the entry's recency

---

Example Usage

cache = AutoExpireCache(capacity=3)

cache.set("a", 1, 60)
cache.set("b", 2, 60)
cache.set("c", 3, 60)
print(cache.size())  # 3

# Access 'a' to make it recently used
cache.get("a")

# Add new entry, 'b' is LRU and gets evicted
cache.set("d", 4, 60)

print(cache.get("a"))  # 1 (still exists)
print(cache.get("b"))  # None (evicted)
print(cache.get("c"))  # 3 (still exists)
print(cache.get("d"))  # 4 (just added)

Follow-Up Discussion Topics

Additional Extensions

1. TTL Refresh on Access: Should get() extend the TTL?

   • "Sliding expiration" vs "absolute expiration"

2. Bulk Operations: mset(), mget() for multiple keys

3. Callbacks: Notify when entries expire

4. Statistics: Hit rate, miss rate, eviction count

---