Requirements

Imagine you're building a collaborative document editing platform like Google Docs, or a sophisticated version control system similar to Git. A core requirement for such systems is the ability to track the history of changes made to a particular entity over time. This history needs to be readily accessible, allowing users to view past states, revert to earlier versions, or understand the evolution of the entity. This problem focuses on designing a concurrent history tracking system, optimized for performance and thread safety. The system should efficiently store snapshots of an object's state at various points in time and provide mechanisms to retrieve these snapshots based on timestamps or version numbers. The system also needs to handle concurrent updates gracefully, ensuring data integrity and consistency even when multiple threads are modifying the tracked entity simultaneously. # Requirements ## Functional Requirements 1. **`track(T state)`:** Tracks the current state `state` of an object of type `T`. This method is the primary way to record the history. The system should automatically assign a version number (sequential integer) and record the timestamp of the update. The state `T` should be deeply copied when tracked, to prevent external modifications from affecting the stored history. Assume `T` is immutable or can be deep-copied. 2. **`getState(int version)`:** Retrieves the state of the object at a specific version. If the version is out of range (less than 1 or greater than the current version), return null or throw an exception (your choice, but be consistent). 3. **`getState(Instant timestamp)`:** Retrieves the state of the object at the point in time closest to the given `timestamp`. If no state exists before the timestamp, return the oldest state. If no state exists after the timestamp, return the newest state. If the history is empty, return null or throw an exception (be consistent). 4. **`getHistory()`:** Returns a list of all versions tracked, in ascending order of version number, as a list of `VersionedState ` objects. 5. **`getCurrentVersion()`:** Returns the current version number. If no version has been tracked yet, return 0. 6. **`prune(int maxVersionsToKeep)`:** Allows you to limit the number of historical versions stored. This is to manage memory consumption. The oldest versions should be removed first, keeping the latest `maxVersionsToKeep` versions. This operation should be thread-safe. 7. **`reset()`:** Clears all history. This should be done atomically. 8. **`getObjectIdentifier()`**: Returns a unique identifier for the object being tracked. This is useful when managing multiple tracked objects within a larger system. ## Non-Functional Requirements 1. **Thread Safety:** The system must be thread-safe, allowing concurrent calls to `track`, `getState`, `getHistory`, `prune`, and `reset` without data corruption or race conditions. Utilize appropriate synchronization mechanisms to achieve this. 2. **Immutability of Stored States:** Once a state is tracked, it must be immutable. The history should store deep copies of the state to prevent external modifications from affecting the stored history. 3. **Efficiency:** The `getState(Instant timestamp)` method should be reasonably efficient. Consider using an appropriate data structure for storing the history to allow for fast lookups by timestamp. Binary search is a good candidate. 4. **Memory Management:** The `prune` method should effectively limit the memory consumption of the system. 5. **Extensibility:** Consider how the system could be extended to support different state types (`T`) or different storage mechanisms (e.g., persisting the history to disk). 6. **Modularity:** Design the system with clear separation of concerns, making it easy to understand, maintain, and modify. 7. **Testability:** The code should be easily testable. Use dependency injection or other techniques to facilitate unit testing and integration testing. Consider the different concurrency scenarios you'll need to test. ## Core Entities 1. **`HistoryTracker `:** The main class responsible for tracking the history of an object. It will provide the core API methods (`track`, `getState`, `getHistory`, `prune`, `reset`). This is the CLASS you will implement. 2. **`VersionedState `:** A simple data class or record that encapsulates the state of an object at a particular version and timestamp. This is a DATA structure (POJO). It might have fields for version number, timestamp, and the actual state (`T`). Should be immutable. 3. **`ObjectIdentifier`:** An interface or class that represents a unique identifier for an object being tracked. Implementations could be based on UUIDs, object IDs, or other suitable mechanisms.

Design an concurrent History tracking system where we can store and track history of registered entities. We should be able to onboard service and their entities to our system and start tracking

Requirements

Interview Simulation

Functional Requirements

💡 Interview Tip

Non-Functional Requirements

Core Entity Identification

Premium Content