Time Based Key-Value Store

Med

#0935Time: `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.21 companies

Patterns

Design

Algorithms

Binary Search

Data structures

Hash Table String

Companies

Airbnb Snowflake VMware eBay

Prompt

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 <= 10⁷
All the timestamps timestamp of set are strictly increasing.
At most 2 * 10⁵ calls will be made to set and get.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

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.
```
1class Pair {2    int timestamp;3    String value;4    Pair(int timestamp, String value) { ... }5}6Map<String, List<Pair>> map;
```
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.
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 "".

Walkthrough

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.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class TimeMap {7    private class Pair {8        int timestamp;9        String value;10 11        Pair(int timestamp, String value) {12            this.timestamp = timestamp;13            this.value = value;14        }15    }16 17    private Map<String, List<Pair>> store;18 19    public TimeMap() {20        store = new HashMap<>();21    }22 23    public void set(String key, String value, int timestamp) {24        // computeIfAbsent gets the list or creates it if it doesn't exist.25        store.computeIfAbsent(key, k -> new ArrayList<>()).add(new Pair(timestamp, value));26    }27 28    public String get(String key, int timestamp) {29        if (!store.containsKey(key)) {30            return "";31        }32 33        List<Pair> pairs = store.get(key);34        // Linear scan from the end to find the largest timestamp <= target timestamp35        for (int i = pairs.size() - 1; i >= 0; i--) {36            if (pairs.get(i).timestamp <= timestamp) {37                return pairs.get(i).value;38            }39        }40 41        return "";42    }43}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Data Structure: The data structure is identical to the previous approach: a HashMap<String, List<Pair>>, where Pair holds a timestamp and a value.
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.
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.

Walkthrough

This approach builds upon the first one by improving the performance of the get method. The set method and the underlying data structure (HashMap<String, List<Pair>>) 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.

1import java.util.ArrayList;2import java.util.HashMap;3import java.util.List;4import java.util.Map;5 6class TimeMap {7    private class Pair {8        int timestamp;9        String value;10 11        Pair(int timestamp, String value) {12            this.timestamp = timestamp;13            this.value = value;14        }15    }16 17    private Map<String, List<Pair>> store;18 19    public TimeMap() {20        store = new HashMap<>();21    }22 23    public void set(String key, String value, int timestamp) {24        store.computeIfAbsent(key, k -> new ArrayList<>()).add(new Pair(timestamp, value));25    }26 27    public String get(String key, int timestamp) {28        if (!store.containsKey(key)) {29            return "";30        }31 32        List<Pair> pairs = store.get(key);33        String result = "";34        int low = 0;35        int high = pairs.size() - 1;36 37        // Binary search to find the desired timestamp38        while (low <= high) {39            int mid = low + (high - low) / 2;40            if (pairs.get(mid).timestamp <= timestamp) {41                // This is a potential answer. Store it and search for a better one in the right half.42                result = pairs.get(mid).value;43                low = mid + 1;44            } else {45                // This timestamp is too large. Search in the left half.46                high = mid - 1;47            }48        }49        return result;50    }51}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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); */

1class 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); */

1class 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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem