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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
package main
import "fmt"
type TimeBucket struct {
entries []TimeEntry
}
type TimeEntry struct {
time int
value string
}
type TimeMap struct {
buckets map[string]*TimeBucket
}
func (bucket *TimeBucket) insertOrdered(time int, value string) {
// 1. Binary Search to find the correct index
index := bucket.insertionIndex(time) // This is exactly where the item needs to go
// 2. Slice Primitives to perform the insertion
// First, append a zero-value element to grow the slice safely (handles allocation)
bucket.entries = append(bucket.entries, TimeEntry{})
// Next, copy the elements over by 1 position to the right to make room
copy(bucket.entries[index+1:], bucket.entries[index:])
// Finally, drop the new item into the open slot
bucket.entries[index] = TimeEntry{
time: time,
value: value,
}
}
func (bucket *TimeBucket) insertionIndex(time int) int {
low, high := 0, len(bucket.entries)
for low < high {
// Calculate mid carefully to prevent integer overflow
mid := low + (high-low)/2
if bucket.entries[mid].time <= time {
low = mid + 1
} else {
high = mid
}
}
return low
}
func Constructor() TimeMap {
return TimeMap{
buckets: map[string]*TimeBucket{},
}
}
func (this *TimeMap) Set(key string, value string, timestamp int) {
bucket, okay := this.buckets[key]
if !okay {
this.buckets[key] = &TimeBucket{
entries: []TimeEntry{},
}
bucket = this.buckets[key]
}
bucket.insertOrdered(timestamp, value)
}
func (this *TimeMap) Get(key string, timestamp int) string {
bucket, okay := this.buckets[key]
if !okay {
return ""
}
idx := bucket.insertionIndex(timestamp)
if idx > 0 {
idx = idx - 1
}
entry := bucket.entries[idx]
if entry.time > timestamp {
return ""
} else {
return entry.value
}
}
func main() {
timeMap := Constructor()
timeMap.Set("foo", "bar", 1) // store the key "foo" and value "bar" along with timestamp = 1.
fmt.Println(timeMap.Get("foo", 1)) // return "bar"
fmt.Println(timeMap.Get("foo", 3)) // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
timeMap.Set("foo", "bar2", 4) // store the key "foo" and value "bar2" along with timestamp = 4.
fmt.Println(timeMap.Get("foo", 4)) // return "bar2"
fmt.Println(timeMap.Get("foo", 5)) // return "bar2"
}
|
