ASAPUtils
The signal
This combines two data structures:
- hash map: O(1) average lookup of one key’s history,
- sorted vector/array: O(log n) lookup by timestamp inside that history.
The timestamps arrive in increasing order, so set is an append. get is a predecessor query:
find the greatest timestamp <= query.
C++ implementation
class TimeMap {
unordered_map<string, vector<pair<int,string>>> data;
public:
void set(string key, string value, int timestamp) {
data[key].push_back({timestamp, value});
}
string get(string key, int timestamp) {
auto& values = data[key];
int l = 0, r = values.size() - 1, answer = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (values[mid].first <= timestamp) {
answer = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return answer < 0 ? "" : values[answer].second;
}
};
JavaScript implementation
class TimeMap {
constructor() {
this.data = new Map();
}
set(key, value, timestamp) {
if (!this.data.has(key)) this.data.set(key, []);
this.data.get(key).push([timestamp, value]);
}
get(key, timestamp) {
const values = this.data.get(key) ?? [];
let l = 0, r = values.length - 1, answer = -1;
while (l <= r) {
const mid = l + Math.floor((r - l) / 2);
if (values[mid][0] <= timestamp) {
answer = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return answer < 0 ? '' : values[answer][1];
}
}
Why remember answer
Finding one valid timestamp is not enough; a later valid one is better. Store the candidate, then move right. If no candidate was ever stored, every timestamp was too late.
Complexity
set is O(1) amortised because it appends. get is O(log k), where k is the number of values stored
for that key. Total storage across keys is O(n).
Traps
- Keeping one global timestamp list and mixing unrelated keys.
- Returning immediately on an exact-less-than match instead of finding the rightmost valid one.
- Sorting after each set despite the increasing-timestamp guarantee.
- Using a plain JavaScript object carelessly for arbitrary string keys;
Mapis explicit and safe. - Forgetting the empty-key or too-early query case.
Blank re-solve prompt
Implement append-only set and predecessor get. State why a valid mid moves the search right rather than ending it.