Requirements

Imagine you're building a high-performance service, and you need a blazingly fast, in-memory cache to avoid hitting slower data sources repeatedly. Your task is to design and implement a robust, thread-safe, and extensible in-memory cache library. This isn't just about storing and retrieving data; it's about building a core component that can adapt to various eviction policies, handle concurrent access gracefully, and provide a consistent interface for different data types. The goal is to create a cache that is easy to integrate, maintain, and extend as the needs of the application evolve. Consider the trade-offs between performance, memory usage, and complexity. # Requirements ## Functional Requirements 1. **Basic Cache Operations:** * `put(key, value, ttl)`: Inserts a key-value pair into the cache with an optional Time-To-Live (TTL) in seconds. If the key already exists, update the value and reset the TTL. If TTL is not provided or is invalid (<=0), the entry should persist indefinitely (until evicted by memory constraints). The key and value can be of any Java type. * `get(key)`: Retrieves the value associated with a key. Returns the value if present and the entry hasn't expired. Returns `null` if the key is not found or the entry has expired. * `remove(key)`: Removes the key-value pair associated with a given key. Returns `true` if the key was found and removed, `false` otherwise. * `clear()`: Removes all entries from the cache. * `size()`: Returns the number of entries currently in the cache. 2. **Eviction Policies:** * Implement at least two eviction policies: * **Least Recently Used (LRU):** Evicts the least recently accessed entry when the cache reaches its maximum capacity. * **Time-To-Live (TTL) based:** Evicts entries that have exceeded their specified TTL, prioritizing older entries if multiple entries are expired. 3. **Maximum Capacity:** * The cache should have a configurable maximum capacity (number of entries). Once the capacity is reached, the eviction policy should be triggered to make room for new entries. 4. **Expiration:** * Implement expiration based on TTL (Time-To-Live). Entries should automatically be removed from the cache after their TTL expires. Expired entries should not be returned by `get()`. 5. **Metrics:** * Provide basic metrics: * `hitCount()`: Returns the number of successful `get()` operations. * `missCount()`: Returns the number of unsuccessful `get()` operations (key not found or expired). ## Non-Functional Requirements 1. **Thread Safety:** The cache must be thread-safe, allowing concurrent access from multiple threads without data corruption or race conditions. Use appropriate synchronization mechanisms (e.g., locks, concurrent data structures). 2. **Extensibility:** The design should be extensible to easily add new eviction policies without modifying the core cache implementation. Consider using the Strategy pattern. 3. **Modularity:** The codebase should be well-modularized, with clear separation of concerns. Eviction policies, data storage, and expiration management should be independent components. 4. **Testability:** The code should be designed to be easily testable, with clear interfaces and minimal dependencies. Write unit tests to verify the correctness of the cache operations and eviction policies. 5. **Performance:** The cache should provide fast access to cached data (ideally O(1) for `get`, `put`, and `remove`). Choose appropriate data structures and algorithms to optimize performance. 6. **Memory Efficiency:** The cache should use memory efficiently. Avoid unnecessary object creation and consider the memory overhead of the chosen data structures. 7. **Configuration:** The cache should be configurable with respect to eviction policy and maximum capacity. ## Core Entities 1. **Cache:** The main class that provides the API for interacting with the cache. It should encapsulate the data store, eviction policy, and expiration management. 2. **CacheEntry:** A class representing a single entry in the cache, containing the key, value, and potentially metadata like TTL and last access time. 3. **EvictionPolicy:** An interface or abstract class that defines the contract for eviction policies. Implementations would include LRU and TTL. 4. **DataStore:** An abstraction to hold the actual cache data. This allows for potentially swapping different data structures, such as HashMap, ConcurrentHashMap, or a custom data structure. 5. **ExpiryManager:** A component to handle expiration of entries based on TTL. It might use a background thread to periodically check for expired entries or rely on lazy expiration during `get()` operations. 6. **CacheStats:** A class to track cache hit and miss metrics.

You are required to implement an in-memory cache module/library which you will embed in your application to improve the application performance, by holding heavily accessed (read/written) application

Requirements

Interview Simulation

Functional Requirements

💡 Interview Tip

Non-Functional Requirements

Core Entity Identification

Premium Content