Requirements

Let's design a key-value store with indexing capabilities. Think of it as a simplified, in-memory database. The core idea is to store data (values) associated with keys and provide efficient retrieval not just by key (primary index) but also by other attributes of the value itself (secondary indices). This is crucial for supporting various query patterns beyond simple key lookups. We need to support multiple, dynamic secondary indices. A real-world example would be storing customer records and needing to look them up not just by customer ID (the key) but also by email address or zip code. We will focus on building a system that allows adding, retrieving, updating, and deleting key-value pairs, along with creating and using secondary indices on the values. # Requirements ## Functional Requirements 1. **Put (Key, Value):** Store a value associated with a key. If the key already exists, overwrite the existing value. 2. **Get (Key):** Retrieve the value associated with a key. Return null if the key does not exist. 3. **Delete (Key):** Remove the key-value pair associated with a key. 4. **Create Index (AttributeName):** Create a secondary index on the specified attribute of the value. The attribute must be a top-level field in the Value object. The store should iterate through all existing data to populate the index *upon creation*. It should throw an exception if index already exists. 5. **Query Index (AttributeName, AttributeValue):** Retrieve all keys whose associated values have the specified attribute equal to the specified value. Return an empty set if the index does not exist or if no values match. The values in the value objects should be of primitive types for indexing (String, Integer, Boolean etc.). 6. **Update Index on Put (Key, Value):** When a new key-value pair is added (or updated), the secondary indices must be updated accordingly. This means adding the key to any relevant index entries and removing the key from old index entries if the indexed attribute has changed. 7. **Update Index on Delete (Key):** When a key-value pair is deleted, the secondary indices must be updated to remove the key from any relevant index entries. 8. **Index Persistence**: Optionally persist the created indexes to disk so they can be reloaded when the application restarts. ## Non-Functional Requirements 1. **Thread Safety:** The key-value store must be thread-safe, allowing multiple concurrent operations (puts, gets, deletes, index creations, and queries) without data corruption or race conditions. Consider both read and write concurrency. 2. **Extensibility:** The design should be extensible to support different index types (e.g., range indexes, full-text indexes) in the future without major code changes. This can be achieved using appropriate design patterns. 3. **Modularity:** The code should be well-modularized, with clear separation of concerns. The indexing logic should be decoupled from the core key-value store logic. 4. **Testability:** The code should be easily testable, with unit tests covering all major functionalities and edge cases. Mocking external dependencies should be possible. 5. **Performance:** While extreme performance isn't the primary focus, operations should be reasonably efficient. Index lookups should be significantly faster than iterating through all key-value pairs. Avoid O(n) complexity where possible, especially on indexed lookups. 6. **Error Handling:** Implement robust error handling, including appropriate exception handling for invalid inputs, concurrent access issues, and index creation failures. 7. **Index Data Types:** The current implementation only supports primitive type indices (String, Integer, Boolean, etc.). The design should be extensible to handle custom index types in the future. ## Core Entities 1. **KeyValueStore:** The main class responsible for storing key-value pairs and managing indices. It should provide the put, get, delete, createIndex, and queryIndex methods. 2. **Index:** An interface for different index types. It should provide methods for adding, removing, and querying indexed values. Implementations could include HashMap-based indices, B-Tree indices, etc. 3. **HashMapIndex:** A concrete implementation of the Index interface using a HashMap to store the indexed values. This is suitable for equality-based lookups. 4. **Value:** Represents the structure of the data being stored in the key-value store. The assumption is the value object consists of primitive types. 5. **IndexManager:** Manages the creation, storage, and retrieval of indices. Ensures thread-safe access to indices.

Design a key value store and an Index.

Requirements

Interview Simulation

Functional Requirements

💡 Interview Tip

Non-Functional Requirements

Core Entity Identification

Premium Content