Sponsored
Sponsored
This approach uses a HashMap where each key points to a sorted list of timestamp-value pairs. The 'set' function appends the value along with the timestamp to the list associated with the key. The 'get' function retrieves the value at a particular timestamp by performing a binary search to find the rightmost timestamp less than or equal to the requested timestamp.
Time Complexity: O(log n) for the 'get' operation and O(1) for the 'set' operation in terms of inserting, where n is the number of entries per key.
Space Complexity: O(n), where n is the number of entries in the TimeMap.
1from bisect import bisect_right
2class TimeMap:
3 def __init__(self):
4 self.store = {}
5 def set(self, key: str, value: str, timestamp: int) -> None:
6 if key not in self.store:
7 self.store[key] = []
8 self.store[key].append((timestamp, value))
9 def get(self, key: str, timestamp: int) -> str:
10 if key not in self.store:
11 return ""
12 values = self.store[key]
13 i = bisect_right(values, (timestamp, chr(127)))
14 if i == 0:
15 return ""
16 return values[i-1][1]In the Python solution, we employ the 'bisect_right' function from the 'bisect' module to perform a binary search. The key-value pairs are stored such that each key corresponds to a list of (timestamp, value) tuples. The 'set' method stores the new data point in logarithmic time complexity due to the sorted insertion. The 'get' method uses binary search to efficiently find the largest timestamp less than or equal to the given timestamp.
This approach is similar, but instead of using a helper library for the binary search, we implement it manually. This approach provides more control over the binary search process.
Time Complexity: O(log n) for the 'get' operation and O(1) for the 'set' operation, where n is the number of entries per key.
Space Complexity: O(n) total space used by the data structure, where n is total number of stored key-value pairs.
1import java.util.*;
2In Java, we utilize a HashMap to store a List of Pair objects for each key. Each Pair object contains a timestamp and its corresponding value. For retrieval, we perform manual binary search logic to find the appropriate timestamp efficiently in logarithmic time.