Time Based Key-Value Store
Time Based Key-Value Store is a medium binary search problem solved with the basics pattern.
The best approach, optimal (binary search per key), runs in O(1) set, O(log m) get time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan the history backwards) up.
Problem
Build a class TimeMap that remembers every value ever written for a key, together with the time it was written. TimeMap() creates an empty store.
set(String key, String value, int timestamp) records that key held value at time timestamp. get(String key, int timestamp) returns the value that key held at time timestamp: the value from the set with the largest timestamp that is not greater than timestamp. If key has no such set, return an empty string "".
The timestamps given to set only ever increase.
Examples
Example 1
- Input
TimeMap(), set("city", "pune", 3), set("city", "goa", 8), get("city", 2), get("city", 3), get("city", 7), get("city", 20)- Output
"", "pune", "pune", "goa"- Why
- Nothing was stored for "city" at or before time 2; at time 7 the latest value written is the one from time 3.
Example 2
- Input
TimeMap(), set("a", "x", 1), set("b", "y", 2), get("b", 1), get("a", 5), get("c", 5)- Output
"", "x", ""- Why
- Each key has its own history, and a key that was never set always returns an empty string.
Constraints
1 <= key.length, value.length <= 100; keys and values use lowercase English letters and digits.1 <= timestamp <= 10^7- The timestamps passed to
setare strictly increasing across all calls. - At most
2 * 10^5calls tosetandgetin total.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan the history backwards) | O(1) set, O(m) get | O(n) |
| Optimal (binary search per key) | O(1) set, O(log m) get | O(n) |
1Brute force (scan the history backwards)
O(1) set, O(m) getA `get` may look at all m versions stored for that key.O(n)Every `set` stores one entry.Map each key to a list of (timestamp, value) pairs in the order they were set, which is increasing time. For get, walk that list from the newest entry backwards and return the first value whose timestamp is not after the query.
- set: append (timestamp, value) to the key's list (create the list if needed).
- get: if the key has no list, return "".
- Walk the list from the last entry to the first; return the value of the first entry with time <= timestamp.
- If none qualifies, return "".
class TimeMap {
private final Map<String, List<Integer>> times = new HashMap<>();
private final Map<String, List<String>> values = new HashMap<>();
public TimeMap() {}
public void set(String key, String value, int timestamp) {
times.computeIfAbsent(key, k -> new ArrayList<>()).add(timestamp);
values.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
}
public String get(String key, int timestamp) {
List<Integer> ts = times.get(key);
if (ts == null) return "";
for (int i = ts.size() - 1; i >= 0; i--) {
if (ts.get(i) <= timestamp) return values.get(key).get(i);
}
return "";
}
}class TimeMap:
def __init__(self):
self.times = defaultdict(list)
self.values = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.times[key].append(timestamp)
self.values[key].append(value)
def get(self, key: str, timestamp: int) -> str:
ts = self.times.get(key)
if not ts:
return ""
for i in range(len(ts) - 1, -1, -1):
if ts[i] <= timestamp:
return self.values[key][i]
return ""class TimeMap {
unordered_map<string, vector<int>> times;
unordered_map<string, vector<string>> values;
public:
TimeMap() {}
void set(string key, string value, int timestamp) {
times[key].push_back(timestamp);
values[key].push_back(value);
}
string get(string key, int timestamp) {
auto it = times.find(key);
if (it == times.end()) return "";
const vector<int>& ts = it->second;
for (int i = (int)ts.size() - 1; i >= 0; i--) {
if (ts[i] <= timestamp) return values[key][i];
}
return "";
}
};class TimeMap {
constructor() {
this.times = new Map();
this.values = new Map();
}
set(key, value, timestamp) {
if (!this.times.has(key)) {
this.times.set(key, []);
this.values.set(key, []);
}
this.times.get(key).push(timestamp);
this.values.get(key).push(value);
}
get(key, timestamp) {
const ts = this.times.get(key);
if (ts === undefined) return "";
for (let i = ts.length - 1; i >= 0; i--) {
if (ts[i] <= timestamp) return this.values.get(key)[i];
}
return "";
}
}2Optimal (binary search per key)
O(1) set, O(log m) getAppending is constant time; the binary search halves the m versions of the key each step.O(n)Every `set` stores one timestamp and one value.Each key's timestamps are stored in increasing order, so its history is a sorted list. A get is then a search for the last timestamp <= t: binary search for the first index whose timestamp is greater than t (an upper bound); the entry just before that index is the answer, and if the index is 0 nothing qualifies.
- set: append the timestamp and the value to the key's two parallel lists.
- get: if the key is missing, return "".
- Binary search with lo = 0, hi = size: while lo < hi, mid = (lo + hi) / 2; if ts[mid] <= t then lo = mid + 1, else hi = mid.
- If lo == 0 return ""; otherwise return values[lo - 1].
class TimeMap {
private final Map<String, List<Integer>> times = new HashMap<>();
private final Map<String, List<String>> values = new HashMap<>();
public TimeMap() {}
public void set(String key, String value, int timestamp) {
times.computeIfAbsent(key, k -> new ArrayList<>()).add(timestamp);
values.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
}
public String get(String key, int timestamp) {
List<Integer> ts = times.get(key);
if (ts == null) return "";
int lo = 0, hi = ts.size();
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (ts.get(mid) <= timestamp) lo = mid + 1;
else hi = mid;
}
return lo == 0 ? "" : values.get(key).get(lo - 1);
}
}class TimeMap:
def __init__(self):
self.times = defaultdict(list)
self.values = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.times[key].append(timestamp)
self.values[key].append(value)
def get(self, key: str, timestamp: int) -> str:
ts = self.times.get(key)
if not ts:
return ""
lo, hi = 0, len(ts)
while lo < hi:
mid = (lo + hi) // 2
if ts[mid] <= timestamp:
lo = mid + 1
else:
hi = mid
return "" if lo == 0 else self.values[key][lo - 1]class TimeMap {
unordered_map<string, vector<int>> times;
unordered_map<string, vector<string>> values;
public:
TimeMap() {}
void set(string key, string value, int timestamp) {
times[key].push_back(timestamp);
values[key].push_back(value);
}
string get(string key, int timestamp) {
auto it = times.find(key);
if (it == times.end()) return "";
const vector<int>& ts = it->second;
int lo = 0, hi = ts.size();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (ts[mid] <= timestamp) lo = mid + 1;
else hi = mid;
}
return lo == 0 ? "" : values[key][lo - 1];
}
};class TimeMap {
constructor() {
this.times = new Map();
this.values = new Map();
}
set(key, value, timestamp) {
if (!this.times.has(key)) {
this.times.set(key, []);
this.values.set(key, []);
}
this.times.get(key).push(timestamp);
this.values.get(key).push(value);
}
get(key, timestamp) {
const ts = this.times.get(key);
if (ts === undefined) return "";
let lo = 0, hi = ts.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (ts[mid] <= timestamp) lo = mid + 1;
else hi = mid;
}
return lo === 0 ? "" : this.values.get(key)[lo - 1];
}
}Edge cases to test
getwith a timestamp earlier than the firstsetfor that keygetwith exactly the timestamp of asetgetfor a key that was never set- Many versions of one key, queried between versions
Hints
Hint 1
For a single key, the timestamps arrive already sorted, because set timestamps only grow. Keep each key's history in a list in that order.
Hint 2
In a sorted list of timestamps, you want the last one that is <= t. Which classic search finds that in O(log n)?
Hint 3
Binary search for the first timestamp that is greater than t; the entry just before it (if any) holds the answer.
FAQ
What is the best time complexity for Time Based Key-Value Store?
Optimal (binary search per key) runs in O(1) set, O(log m) get time and O(n) extra space. Appending is constant time; the binary search halves the m versions of the key each step.
Which pattern does Time Based Key-Value Store use?
It is a binary search problem that uses the basics pattern. Other problems with the same pattern: Fundamentals, Binary Search.
Is there a brute force solution for Time Based Key-Value Store?
Yes. Brute force (scan the history backwards) takes O(1) set, O(m) get time and O(n) space. Map each key to a list of (timestamp, value) pairs in the order they were set, which is increasing time.
Which edge cases should I test for Time Based Key-Value Store?
get with a timestamp earlier than the first set for that key; get with exactly the timestamp of a set; get for a key that was never set; Many versions of one key, queried between versions.