# Time Based Key-Value Store **Difficulty:** MEDIUM [External](https://leetcode.com/problems/time-based-key-value-store) Canonical: https://scaleengineer.com/dsa/problems/time-based-key-value-store **Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design) **Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search) **Data structures:** Hash Table, String **Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Snowflake](https://scaleengineer.com/companies/snowflake), [VMware](https://scaleengineer.com/companies/vmware), [eBay](https://scaleengineer.com/companies/ebay), [Lyft](https://scaleengineer.com/companies/lyft), [Netflix](https://scaleengineer.com/companies/netflix), [Databricks](https://scaleengineer.com/companies/databricks), [Confluent](https://scaleengineer.com/companies/confluent), [Axon](https://scaleengineer.com/companies/axon), [Flexport](https://scaleengineer.com/companies/flexport), [Nextdoor](https://scaleengineer.com/companies/nextdoor), [Anduril](https://scaleengineer.com/companies/anduril), [Verkada](https://scaleengineer.com/companies/verkada), [Instacart](https://scaleengineer.com/companies/instacart), [CrowdStrike](https://scaleengineer.com/companies/crowdstrike), [Compass](https://scaleengineer.com/companies/compass), [CARS24](https://scaleengineer.com/companies/cars24), [Coinbase](https://scaleengineer.com/companies/coinbase), [Notion](https://scaleengineer.com/companies/notion), [OpenAI](https://scaleengineer.com/companies/openai), [Gusto](https://scaleengineer.com/companies/gusto) --- ## Problem Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp. Implement the `TimeMap` class: * `TimeMap()` Initializes the object of the data structure. * `void set(String key, String value, int timestamp)` Stores the key `key` with the value `value` at the given time `timestamp`. * `String get(String key, int timestamp)` Returns a value such that `set` was called previously, with `timestamp_prev <= timestamp`. If there are multiple such values, it returns the value associated with the largest `timestamp_prev`. If there are no values, it returns `""`. **Example 1:** **Input** ["TimeMap", "set", "get", "get", "set", "get", "get"] [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]] **Output** [null, null, "bar", "bar", null, "bar2", "bar2"] **Explanation** TimeMap timeMap = new TimeMap(); timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1. timeMap.get("foo", 1); // return "bar" timeMap.get("foo", 3); // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar". timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4. timeMap.get("foo", 4); // return "bar2" timeMap.get("foo", 5); // return "bar2" **Constraints:** * `1 <= key.length, value.length <= 100` * `key` and `value` consist of lowercase English letters and digits. * `1 <= timestamp <= 107` * All the timestamps `timestamp` of `set` are strictly increasing. * At most `2 * 105` calls will be made to `set` and `get`. # Approaches ## HashMap with Linear Scan This approach uses a `HashMap` to store keys, where each key maps to a list of `(timestamp, value)` pairs. When a value is set, it's appended to the list associated with its key. The `get` operation involves a linear scan through this list to find the appropriate value. **Time:** `set`: O(1) on average. Appending to an `ArrayList` is an amortized O(1) operation. `get`: O(L), where L is the number of entries for the given key. In the worst case, we might have to scan the entire list. · **Space:** O(N), where N is the total number of `set` calls. We need to store each `(key, value, timestamp)` triplet provided. **Pros:** Simple to understand and implement.; The `set` operation is very fast, with an average time complexity of O(1). **Cons:** The `get` operation has a time complexity of O(L), where L is the number of timestamps for a key. This can be inefficient if a key is associated with a large number of values. ### Explanation The core idea is to use a `HashMap` for quick access to the data associated with a key. The value part of this map is a list that stores all the historical `(value, timestamp)` data for that key. For the `set` operation, we retrieve the list for the given key. If no list exists, we create one. Then, we simply add a new pair containing the `value` and `timestamp` to this list. Because the problem states that timestamps for `set` calls are strictly increasing, appending to the list maintains the sorted order of timestamps. For the `get` operation, we first retrieve the list of pairs for the key. To find the value with the largest `timestamp_prev <= timestamp`, we can perform a linear scan. A simple and effective way is to scan the list from the end. The first entry we encounter whose timestamp is less than or equal to the target `timestamp` is our answer, as the list is sorted. If we scan the entire list and find no such entry, it means no valid value exists, and we return an empty string. ```java import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; class TimeMap { private class Pair { int timestamp; String value; Pair(int timestamp, String value) { this.timestamp = timestamp; this.value = value; } } private Map> store; public TimeMap() { store = new HashMap<>(); } public void set(String key, String value, int timestamp) { // computeIfAbsent gets the list or creates it if it doesn't exist. store.computeIfAbsent(key, k -> new ArrayList<>()).add(new Pair(timestamp, value)); } public String get(String key, int timestamp) { if (!store.containsKey(key)) { return ""; } List pairs = store.get(key); // Linear scan from the end to find the largest timestamp <= target timestamp for (int i = pairs.size() - 1; i >= 0; i--) { if (pairs.get(i).timestamp <= timestamp) { return pairs.get(i).value; } } return ""; } } ``` ### Algorithm 1. **Data Structure**: Use a `HashMap` where keys are the input `String key` and values are a `List` of custom `Pair` objects. Each `Pair` object will store an `int timestamp` and a `String value`. ```java class Pair { int timestamp; String value; Pair(int timestamp, String value) { ... } } Map> map; ``` 2. **`set(key, value, timestamp)`**: * Check if the `key` exists in the `HashMap`. If not, create a new `ArrayList` for it and add it to the map. * Add the new `Pair(timestamp, value)` to the end of the list for the given `key`. Since the problem guarantees that timestamps in `set` calls are strictly increasing, the list will automatically be sorted by timestamp. 3. **`get(key, timestamp)`**: * If the `key` does not exist in the map, return an empty string `""`. * Retrieve the list of `Pair` objects for the given `key`. * Iterate through the list **backwards**, from the last element to the first. * For each `Pair`, check if its `timestamp` is less than or equal to the target `timestamp`. * The first one that satisfies this condition is the correct answer because we are iterating from the largest timestamp downwards. Return its `value`. * If the loop completes without finding any suitable timestamp (i.e., all stored timestamps are greater than the target `timestamp`), return `""`. ## HashMap with Binary Search This approach optimizes the `get` operation by leveraging the sorted nature of the timestamps. It uses the same `HashMap` to map keys to a list of `(timestamp, value)` pairs. Since the timestamps for each key are stored in increasing order, we can use binary search instead of a linear scan to find the correct value efficiently. **Time:** `set`: O(1) on average. `get`: O(log L), where L is the number of entries for the given key. Binary search provides a significant performance improvement over linear scan. · **Space:** O(N), where N is the total number of `set` calls. The space usage is identical to the linear scan approach. **Pros:** Highly efficient `get` operation with logarithmic time complexity, making it suitable for large datasets.; The `set` operation remains very fast at O(1) on average. **Cons:** The implementation of binary search is slightly more complex than a simple loop. ### Explanation This approach builds upon the first one by improving the performance of the `get` method. The `set` method and the underlying data structure (`HashMap>`) remain the same. The key insight is that since all timestamps for `set` calls are strictly increasing, the list of pairs for any given key is inherently sorted by timestamp. A sorted list is a perfect candidate for binary search. When `get(key, timestamp)` is called, we can perform a binary search on the list of pairs to find the value associated with the largest `timestamp_prev` that is less than or equal to the given `timestamp`. The binary search algorithm needs to be tailored to find not an exact match, but the 'floor' element. We search for `timestamp`. If we find an element with `timestamp_prev <= timestamp`, we know it's a possible answer, but there might be a better one (with a larger timestamp) to its right. So, we record this answer and continue searching in the right half. If we find an element with `timestamp_prev > timestamp`, it's not a valid answer, and we must search in the left half. This process efficiently narrows down the search space, reducing the time complexity significantly. ```java import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; class TimeMap { private class Pair { int timestamp; String value; Pair(int timestamp, String value) { this.timestamp = timestamp; this.value = value; } } private Map> store; public TimeMap() { store = new HashMap<>(); } public void set(String key, String value, int timestamp) { store.computeIfAbsent(key, k -> new ArrayList<>()).add(new Pair(timestamp, value)); } public String get(String key, int timestamp) { if (!store.containsKey(key)) { return ""; } List pairs = store.get(key); String result = ""; int low = 0; int high = pairs.size() - 1; // Binary search to find the desired timestamp while (low <= high) { int mid = low + (high - low) / 2; if (pairs.get(mid).timestamp <= timestamp) { // This is a potential answer. Store it and search for a better one in the right half. result = pairs.get(mid).value; low = mid + 1; } else { // This timestamp is too large. Search in the left half. high = mid - 1; } } return result; } } ``` ### Algorithm 1. **Data Structure**: The data structure is identical to the previous approach: a `HashMap>`, where `Pair` holds a `timestamp` and a `value`. 2. **`set(key, value, timestamp)`**: This operation is also identical. We retrieve the list for the `key` (or create it) and append the new `Pair(timestamp, value)`. The list remains sorted by timestamp. 3. **`get(key, timestamp)`**: * If the `key` does not exist in the map, return `""`. * Retrieve the sorted list of `Pair` objects for the `key`. * Instead of a linear scan, perform a **binary search** on this list to find the desired value. * The goal of the binary search is to find the rightmost element whose timestamp is less than or equal to the target `timestamp`. * Initialize `low = 0`, `high = list.size() - 1`, and a variable `result = ""`. * In the binary search loop (`while low <= high`): * Calculate `mid`. * If the timestamp at `mid` is less than or equal to the target `timestamp`, it's a potential candidate. We store its value in `result` and try to find a better candidate (with a larger timestamp) in the right half of the search space by setting `low = mid + 1`. * If the timestamp at `mid` is greater than the target `timestamp`, it's too large. We must search in the left half by setting `high = mid - 1`. * After the loop terminates, `result` will hold the value corresponding to the largest timestamp less than or equal to the target, or `""` if no such value was found. # Solutions ### Java ```java class TimeMap { private Map < String , TreeMap < Integer , String >> ktv = new HashMap <>(); public TimeMap () { } public void set ( String key , String value , int timestamp ) { ktv . computeIfAbsent ( key , k -> new TreeMap <>()). put ( timestamp , value ); } public String get ( String key , int timestamp ) { if (! ktv . containsKey ( key )) { return "" ; } var tv = ktv . get ( key ); Integer t = tv . floorKey ( timestamp ); return t == null ? "" : tv . get ( t ); } } /** * Your TimeMap object will be instantiated and called as such: * TimeMap obj = new TimeMap(); * obj.set(key,value,timestamp); * String param_2 = obj.get(key,timestamp); */ ``` ### CPP ```cpp class TimeMap { public: TimeMap () { } void set ( string key , string value , int timestamp ) { ktv [ key ]. emplace_back ( timestamp , value ); } string get ( string key , int timestamp ) { auto & pairs = ktv [ key ]; pair < int , string > p = { timestamp , string ({ 127 })}; auto i = upper_bound ( pairs . begin (), pairs . end (), p ); return i == pairs . begin () ? "" : ( i - 1 ) -> second ; } private: unordered_map < string , vector < pair < int , string >>> ktv ; }; /** * Your TimeMap object will be instantiated and called as such: * TimeMap* obj = new TimeMap(); * obj->set(key,value,timestamp); * string param_2 = obj->get(key,timestamp); */ ``` ### Python ```python class TimeMap : def __init__ ( self ): self . ktv = defaultdict ( list ) def set ( self , key : str , value : str , timestamp : int ) -> None : self . ktv [ key ]. append (( timestamp , value )) def get ( self , key : str , timestamp : int ) -> str : if key not in self . ktv : return '' tv = self . ktv [ key ] i = bisect_right ( tv , ( timestamp , chr ( 127 ))) return tv [ i - 1 ][ 1 ] if i else '' # Your TimeMap object will be instantiated and called as such: # obj = TimeMap() # obj.set(key,value,timestamp) # param_2 = obj.get(key,timestamp) ```