Time Based Key-Value Store (opens in a new tab) Medium
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.
Example
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"]
Summary
To implement the TimeMap class, we can use a dictionary to store key-value pairs where the value is a list of tuples containing the timestamp and its associated value. To retrieve the value for a key at a certain timestamp, we can use binary search to find the value with the largest timestamp that is less than or equal to the given timestamp.
Solution
Remark The right >= 0 ? values[right][1] : ""; statement in TypeScript (or values[right][1] if right >= 0 else "" in Python) is used to handle edge cases when searching for the largest timestamp that is less than or equal to the given timestamp.
After performing the binary search, if right is still within the range of the values list (i.e., right >= 0), it means that there exists at least one timestamp less than or equal to the given timestamp, so we return the value associated with that timestamp (values[right][1]).
However, if right goes out of range (i.e., right < 0), it means that there is no timestamp less than or equal to the given timestamp. In this case, we return an empty string "" to indicate that there is no value for the given key and timestamp.
In TypeScript
class TimeMap {
private data: Map<string, [number, string][]>;
constructor() {
this.data = new Map();
}
set(key: string, value: string, timestamp: number): void {
if (!this.data.has(key)) {
this.data.set(key, []);
}
this.data.get(key)!.push([timestamp, value]);
}
get(key: string, timestamp: number): string {
if (!this.data.has(key)) {
return "";
}
const values = this.data.get(key)!;
let left = 0;
let right = values.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (values[mid][0] === timestamp) {
return values[mid][1];
} else if (values[mid][0] < timestamp) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right >= 0 ? values[right][1] : "";
}
}In Python
from typing import List, Tuple
class TimeMap:
def __init__(self):
self.data = {}
def set(self, key: str, value: str, timestamp: int) -> None:
if key not in self.data:
self.data[key] = []
self.data[key].append((timestamp, value))
def get(self, key: str, timestamp: int) -> str:
if key not in self.data:
return ""
values = self.data[key]
left, right = 0, len(values) - 1
while left <= right:
mid = left + (right - left) // 2
if values[mid][0] == timestamp:
return values[mid][1]
elif values[mid][0] < timestamp:
left = mid + 1
else:
right = mid - 1
return values[right][1] if right >= 0 else ""Step-by-step explanation
- Define the
TimeMapclass with a private propertydata.datais a Map with string keys and values that are arrays of tuples, where each tuple contains a timestamp (number) and a value (string).
class TimeMap {
private data: Map<string, [number, string][]>;
}- Implement the
constructormethod, which initializes thedataproperty as a new empty Map.
constructor() {
this.data = new Map();
}- Implement the
setmethod, which takes a key, value, and timestamp as input. If the key is not in the data Map, create an empty array for the key. Then, push the timestamp-value tuple into the array associated with the key.
set(key: string, value: string, timestamp: number): void {
if (!this.data.has(key)) {
this.data.set(key, []);
}
this.data.get(key)!.push([timestamp, value]);
}- Implement the
getmethod, which takes a key and timestamp as input. If the key is not in the data Map, return an empty string.
get(key: string, timestamp: number): string {
if (!this.data.has(key)) {
return "";
}
}- Get the array of timestamp-value tuples associated with the key.
const values = this.data.get(key)!;- Initialize
leftandrightpointers to represent the search interval for the binary search.
let left = 0;
let right = values.length - 1;- Perform a binary search to find the largest timestamp that is less than or equal to the input timestamp. If the value at the middle index
midis equal to the timestamp, return the value at that index. If the value is less than the timestamp, updatelefttomid + 1. If the value is greater than the timestamp, updaterighttomid - 1.
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (values[mid][0] === timestamp) {
return values[mid][1];
} else if (values[mid][0] < timestamp) {
left = mid + 1;
} else {
right = mid - 1;
}
}- After the binary search, if the right pointer is greater than or equal to 0, return the value at the right index. This is because the right pointer indicates the largest timestamp that is less than or equal to the input timestamp. If the right pointer is less than 0, return an empty string since there is no value with a timestamp less than or equal to the input timestamp.
return right >= 0 ? values[right][1] : "";Complexity Analysis
Time Complexity
set: The time complexity of the set operation is O(1) since we are just appending a tuple to the list of values for the given key.
get: The time complexity of the get operation is O(log n) where n is the number of values stored for a given key, as we are using binary search to find the value with the largest timestamp less than or equal to the given timestamp.
Space Complexity
The space complexity of this solution is O(k * n) where k is the number of unique keys and n is the average number of values stored for each key. We store the key-value pairs along with their timestamps in a dictionary, and each key has a list of timestamp-value pairs.