The titile of the question clearly shows a key-value dictionary is required. As stated in the Constraints, the set function will give strictly increasing timestamp, implying a sorted array could be easily drawn.
Based on the intuitive data structure above, binary search against the timestamp solves the question .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class TimeMap {
dict: {[k: string]: Array<[string, number]>}
constructor() {
this.dict = {}
}
set(key: string, value: string, timestamp: number): void {
if ( this.dict[key] === undefined ) this.dict[key] = []
this.dict[key].push([value, timestamp])
}
get(key: string, timestamp: number): string {
if ( this.dict[key] === undefined ) this.dict[key] = []
let h = 0
let t = this.dict[key].length
let m
while ( h < t ) {
m = Math.floor((h+t)/2)
if ( this.dict[key][m][1] <= timestamp ) {
h = m + 1
} else {
t = m
}
}
if ( h - 1 >= 0 ) {
return this.dict[key][h-1][0]
} else {
return ""
}
}
}