wordsHEADmain

1 files changed, 97 insertions, 0 deletions

diff --git a/timebucket/main.go b/timebucket/main.go
new file mode 100644
index 0000000..eb3eca1
--- /dev/null
+++ b/timebucket/main.go
@@ -0,0 +1,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"
+}