Practice/Microsoft/Design a key-value store

Design a key-value store

Object Oriented DesignMust

Problem

Design and implement an in-memory caching system that efficiently stores and retrieves data with configurable eviction policies. Your cache must support multiple data types (strings, numbers, lists) and handle automatic expiration of items based on time-to-live (TTL) values or capacity constraints.

The system should support three eviction strategies:

• LRU (Least Recently Used): Remove items that haven't been accessed recently
• LFU (Least Frequently Used): Remove items with the lowest access count
• FIFO (First In First Out): Remove the oldest items first

Your implementation should handle edge cases like concurrent access patterns, expired items, and capacity limits gracefully.

Requirements

1. Implement a CacheSystem class that accepts a maximum capacity and eviction policy
2. Support basic operations: set(), get(), and delete() for key-value pairs
3. Implement TTL (time-to-live) functionality where items expire after a specified duration
4. Support storing and manipulating list data structures with set_list(), get_list(), and list_append() methods
5. Automatically evict items when capacity is reached based on the configured policy
6. Track access patterns (frequency and recency) to support different eviction strategies
7. Handle expired items by removing them on access or through periodic cleanup

Constraints

• 1 ≤ capacity ≤ 10,000
• Keys are non-empty strings with length ≤ 100
• TTL values are non-negative integers (in seconds)
• The cache should handle at least 100,000 operations efficiently
• Time complexity for get and set operations should be O(1) or O(log n)
• Space complexity should be O(capacity)

Examples

Example 1: Basic Operations

` cache = CacheSystem(capacity=3) cache.set("name", "John") cache.set("age", 30) cache.set("city", "NYC")

print(cache.get("name")) # Output: "John" print(cache.get("age")) # Output: 30 `

Example 2: LRU Eviction

` cache = CacheSystem(capacity=2, eviction_policy="LRU") cache.set("a", 1) cache.set("b", 2) cache.get("a") # Access "a", making it recently used cache.set("c", 3) # This evicts "b" since it's least recently used

print(cache.get("b")) # Output: None (evicted) print(cache.get("a")) # Output: 1 (still present) `

Example 3: TTL Expiration

` cache = CacheSystem(capacity=5) cache.set("session", "abc123", ttl=2) # Expires in 2 seconds

print(cache.get("session")) # Output: "abc123" time.sleep(3) print(cache.get("session")) # Output: None (expired) `

Example 4: List Operations

` cache = CacheSystem(capacity=10) cache.set_list("tasks", ["task1", "task2"]) cache.list_append("tasks", "task3")

print(cache.get_list("tasks")) # Output: ["task1", "task2", "task3"] `