# 1. Clarifying Questions - **Are timestamps strictly increasing for a specific key?** While timestamps are typically sequential, we should clarify if we must handle out-of-order `set` operations. - **What is the expected scale of the data?** If a single key has millions of versions, the efficiency of the search within versions becomes critical. - **How should concurrent `set` operations on the same key and timestamp be handled?** Usually, the last write should overwrite the existing value. - **What should be returned if no valid version exists?** Standard behavior is to return `null` or an empty string. **Assumptions:** - Timestamps are of type `long`. - Keys and values are `String`. - Thread safety is required for high-concurrency environments. - Timestamps do not have to be strictly increasing, but they are generally added in chronological order. # 2. Thinking Process - **Data Organization**: Use a primary map to store keys. Each key maps to a time-ordered structure containing its values at different timestamps. - **Efficient Retrieval**: To find the latest value at or before a timestamp ($t \le target$), a sorted structure is needed. Java's `TreeMap` provides `floorEntry(timestamp)`, which performs an efficient binary search-like lookup in $O(\log N)$. - **Concurrency Strategy**: Use a `ConcurrentHashMap` for the top-level keys to allow multiple threads to access different keys simultaneously. For the version history (the `TreeMap`), use synchronization or explicit locks per key to ensure atomicity when adding or reading versions. - **Atomicity**: Ensure that `set` operations are thread-safe such that multiple threads writing to the same key do not corrupt the internal `TreeMap`. # 3. Problem set - **Requirements**: - `void set(String key, String value, long timestamp)`: Stores the value at the given timestamp. - `String get(String key, long timestamp)`: Returns the value such that `timestamp_prev <= timestamp`. - **Constraints**: - Must be thread-safe. - `get` operations should be optimized for speed. - Handle large numbers of versions per key efficiently. # 4. Methodology - **Algorithm**: Binary Search (via TreeMap's NavigableMap interface). - **Data Structure**: `ConcurrentHashMap>`. - **Complexity**: - **Time**: `set`: $O(\log N)$, `get`: $O(\log N)$, where $N$ is the number of versions for a specific key. - **Space**: $O(K \cdot N)$, where $K$ is the number of unique keys and $N$ is the average versions per key. # 5. Solution ```java import java.util.TreeMap; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; /** * A thread-safe, versioned key-value store. */ public class VersionedKVStore { // Primary map for keys. TreeMap is used for versions to enable floorEntry lookups. private final ConcurrentHashMap> store; public VersionedKVStore() { this.store = new ConcurrentHashMap<>(); } /** * Stores a value for a key at a specific timestamp. * Complexity: O(log N) where N is the number of versions for the key. */ public void set(String key, String value, long timestamp) { // Use computeIfAbsent to ensure we have a TreeMap for the key. // TreeMap itself is not thread-safe, so we synchronize on the map instance for that key. TreeMap history = store.computeIfAbsent(key, k -> new TreeMap<>()); synchronized (history) { history.put(timestamp, value); } } /** * Retrieves the latest value for a key at or before the given timestamp. * Complexity: O(log N) due to the binary search performed by floorEntry. */ public String get(String key, long timestamp) { TreeMap history = store.get(key); if (history == null) { return null; } // Synchronize on history to prevent reading while a write is occurring. synchronized (history) { // floorEntry returns the greatest key less than or equal to the given key, or null. Map.Entry entry = history.floorEntry(timestamp); return (entry != null) ? entry.getValue() : null; } } public static void main(String[] args) { VersionedKVStore kv = new VersionedKVStore(); // Example Usage kv.set("foo", "bar", 1); System.out.println(kv.get("foo", 1)); // bar System.out.println(kv.get("foo", 3)); // bar kv.set("foo", "bar2", 4); System.out.println(kv.get("foo", 4)); // bar2 System.out.println(kv.get("foo", 5)); // bar2 System.out.println(kv.get("foo", 0)); // null } } ```