Time Based Key Value Store
Program for Time Based Key-Value Store Problem
Design a time-based key-value store that can:
- Store multiple values for the same key at different timestamps.
- Retrieve a key’s value based on a given timestamp.
set(String key, String value, int timestamp): Stores the given value for a key at the specified timestamp.
get(String key, int timestamp): Returns the most recent value of the key with a timestamp less than or equal to the given one. If no such value exists, return an empty string.
Note: The timestamps will always be in increasing order when calling set.
Output: [null, null, "happy", "happy", null, "sad"]
Constraints:
- 1 <= key.length, value.length <= 100
- key and value only include lowercase English letters and digits.
- 1 <= timestamp <= 1000
Program for Time Based Key-Value Store Solution
Recommendation for Time and Space Complexity – You should aim for a solution with O(1) time for set(), O(logn) time for get(), and O(m * n) space, where n is the total number of values associated with a key, and m is the total number of keys.
Hints for solving problems
Hint 1 :
Can you think of a data structure that is useful for storing key-value pairs? Perhaps a hash-based data structure where we not only store unique elements but also associate additional information with each element?
Hint 2 :
We store key-value pairs in a hash map. In this case, we store the keys as usual, but instead of a single value, we store a list of values, each paired with its corresponding timestamp. This allows us to implement the set() method in O(1). How can you leverage this hash map to implement the get() method?
There are mainly 2 approach to solve this problem-
- Brute Force Method
- Binary Search(Sorted Map) Method
1. Brute Force Method
Store all key-value pairs with timestamps and iterate through the list to find the most recent valid timestamp for a given key, resulting in O(n) lookup time.
- Time complexity: O(1) for set() and O(n) for get().
- Space complexity: O(m∗n)
where n is the total number of unique timestamps associated with a key and m is the total number of keys.
Code
class TimeMap {
public:
unordered_map<string, unordered_map<int, vector<string>>> keyStore;
TimeMap() {}
void set(string key, string value, int timestamp) {
keyStore[key][timestamp].push_back(value);
}
string get(string key, int timestamp) {
if (keyStore.find(key) == keyStore.end()) {
return "";
}
int seen = 0;
for (const auto& [time, _] : keyStore[key]) {
if (time <= timestamp) {
seen = max(seen, time);
}
}
return seen == 0 ? "" : keyStore[key][seen].back();
}
};
public class TimeMap {
private Map<String, Map<Integer, List>>> keyStore;
public TimeMap() {
keyStore = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
if (!keyStore.containsKey(key)) {
keyStore.put(key, new HashMap<>());
}
if (!keyStore.get(key).containsKey(timestamp)) {
keyStore.get(key).put(timestamp, new ArrayList<>());
}
keyStore.get(key).get(timestamp).add(value);
}
public String get(String key, int timestamp) {
if (!keyStore.containsKey(key)) {
return "";
}
int seen = 0;
for (int time : keyStore.get(key).keySet()) {
if (time <= timestamp) {
seen = Math.max(seen, time);
}
}
if (seen == 0) return "";
int back = keyStore.get(key).get(seen).size() - 1;
return keyStore.get(key).get(seen).get(back);
}
}
class TimeMap:
def __init__(self):
self.keyStore = {}
def set(self, key: str, value: str, timestamp: int) -> None:
if key not in self.keyStore:
self.keyStore[key] = {}
if timestamp not in self.keyStore[key]:
self.keyStore[key][timestamp] = []
self.keyStore[key][timestamp].append(value)
def get(self, key: str, timestamp: int) -> str:
if key not in self.keyStore:
return ""
seen = 0
for time in self.keyStore[key]:
if time <= timestamp:
seen = max(seen, time)
return "" if seen == 0 else self.keyStore[key][seen][-1]
class TimeMap {
constructor() {
this.keyStore = new Map();
}
/**
* @param {string} key
* @param {string} value
* @param {number} timestamp
* @return {void}
*/
set(key, value, timestamp) {
if (!this.keyStore.has(key)) {
this.keyStore.set(key, new Map());
}
if (!this.keyStore.get(key).has(timestamp)) {
this.keyStore.get(key).set(timestamp, []);
}
this.keyStore.get(key).get(timestamp).push(value);
}
/**
* @param {string} key
* @param {number} timestamp
* @return {string}
*/
get(key, timestamp) {
if (!this.keyStore.has(key)) {
return "";
}
let seen = 0;
for (let time of this.keyStore.get(key).keys()) {
if (time <= timestamp) {
seen = Math.max(seen, time);
}
}
return seen === 0 ? "" : this.keyStore.get(key).get(seen).at(-1);
}
}
2. Binary Search (Sorted Map) Method
Use a sorted map to store values for each key, with timestamps as the keys in the map. To retrieve a value, perform a binary search on the timestamps to find the largest timestamp less than or equal to the given one. This method is efficient with O(log n) retrieval time.
- Time complexity: O(1) for set() and O(log n) for get().
- Space complexity: O(m∗n)
where n is the total number of unique timestamps associated with a key and m is the total number of keys.
Code
class TimeMap {
public:
unordered_map<string, map<int, string>> m;
TimeMap() {}
void set(string key, string value, int timestamp) {
m[key].insert({timestamp, value});
}
string get(string key, int timestamp) {
auto it = m[key].upper_bound(timestamp);
return it == m[key].begin() ? "" : prev(it)->second;
}
};
public class TimeMap {
private Map<String, TreeMap<Integer, String>> m;
public TimeMap() {
m = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
m.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
}
public String get(String key, int timestamp) {
if (!m.containsKey(key)) return "";
TreeMap<Integer, String> timestamps = m.get(key);
Map.Entry<Integer, String> entry = timestamps.floorEntry(timestamp);
return entry == null ? "" : entry.getValue();
}
}
from sortedcontainers import SortedDict
class TimeMap:
def __init__(self):
self.m = defaultdict(SortedDict)
def set(self, key: str, value: str, timestamp: int) -> None:
self.m[key][timestamp] = value
def get(self, key: str, timestamp: int) -> str:
if key not in self.m:
return ""
timestamps = self.m[key]
idx = timestamps.bisect_right(timestamp) - 1
if idx >= 0:
closest_time = timestamps.iloc[idx]
return timestamps[closest_time]
return ""
class TimeMap {
constructor() {
this.keyStore = new Map();
}
/**
* @param {string} key
* @param {string} value
* @param {number} timestamp
* @return {void}
*/
set(key, value, timestamp) {
if (!this.keyStore.has(key)) {
this.keyStore.set(key, []);
}
this.keyStore.get(key).push([timestamp, value]);
}
/**
* @param {string} key
* @param {number} timestamp
* @return {string}
*/
get(key, timestamp) {
const values = this.keyStore.get(key) || [];
let left = 0;
let right = values.length - 1;
let result = '';
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (values[mid][0] <= timestamp) {
result = values[mid][1];
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
}
