forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0981-time-based-key-value-store.go
45 lines (40 loc) · 960 Bytes
/
0981-time-based-key-value-store.go
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
33
34
35
36
37
38
39
40
41
42
43
44
45
type TimeMap struct {
store map[string][]ValStamp // key : list of [val, timestamp]
}
type ValStamp struct {
Val string
Time int
}
func Constructor() TimeMap {
return TimeMap{store: make(map[string][]ValStamp)}
}
func (this *TimeMap) Set(key string, value string, timestamp int) {
if _, ok := this.store[key]; !ok {
this.store[key] = make([]ValStamp, 0)
}
this.store[key] = append(this.store[key], ValStamp{value, timestamp})
}
func (this *TimeMap) Get(key string, timestamp int) string {
var res string
var values []ValStamp
if _, ok := this.store[key]; ok {
values = this.store[key]
}
l, r := 0, len(values)-1
for l <= r {
mid := l + (r-l)/2
if values[mid].Time <= timestamp {
res = values[mid].Val
l = mid + 1
} else {
r = mid - 1
}
}
return res
}
/**
* Your TimeMap object will be instantiated and called as such:
* obj := Constructor();
* obj.Set(key,value,timestamp);
* param_2 := obj.Get(key,timestamp);
*/