Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 97
Good morning! Here's your coding interview problem for today.

This problem was asked by Stripe.

Write a map implementation with a get function that lets you retrieve the value of a key at a particular time.

It should contain the following methods:
```
set(key, value, time): sets key to value for t = time.
get(key, time): gets the key at t = time.
```
The map should work like this. If we set a key at a particular time, it will maintain that value forever or until it gets set at a later time. In other words, when we get a key at a time, it should return the value that was set for that key set at the most recent time.

Consider the following examples:
```
d.set(1, 1, 0) # set key 1 to value 1 at time 0
d.set(1, 2, 2) # set key 1 to value 2 at time 2
d.get(1, 1) # get key 1 at time 1 should be 1
d.get(1, 3) # get key 1 at time 3 should be 2
d.set(1, 1, 5) # set key 1 to value 1 at time 5
d.get(1, 0) # get key 1 at time 0 should be 1
d.get(1, 10) # get key 1 at time 10 should be 1
d.set(1, 1, 0) # set key 1 to value 1 at time 0
d.set(1, 2, 0) # set key 1 to value 2 at time 0
d.get(1, 0) # get key 1 at time 0 should be 2
d.get(2, 0) # get key 2 at time 0 should be nil
```

Pull request description:
Day97
Resolves #203.

Patch:
diff --git a/README.md b/README.md
index c59f71a..343198e 100644
--- a/README.md
+++ b/README.md
@@ -105,4 +105,5 @@ problems from
 * [Day 94](https://github.com/vaskoz/dailycodingproblem-go/issues/197)
 * [Day 95](https://github.com/vaskoz/dailycodingproblem-go/issues/198)
 * [Day 96](https://github.com/vaskoz/dailycodingproblem-go/issues/200)
+* [Day 97](https://github.com/vaskoz/dailycodingproblem-go/issues/203)
 * [Day 99](https://github.com/vaskoz/dailycodingproblem-go/issues/205)
diff --git a/day97/problem.go b/day97/problem.go
new file mode 100644
index 0000000..3b83cf3
--- /dev/null
+++ b/day97/problem.go
@@ -0,0 +1,42 @@
+package day97
+
+import (
+	"sort"
+)
+
+// TimestampedValue represents the value set at a particular time.
+type TimestampedValue struct {
+	Time  int
+	Value interface{}
+}
+
+// TimeMap is a map that is aware of changes over time.
+type TimeMap struct {
+	data map[interface{}][]*TimestampedValue
+}
+
+// NewTimeMap returns a new timestamp aware map.
+func NewTimeMap() *TimeMap {
+	return &TimeMap{make(map[interface{}][]*TimestampedValue)}
+}
+
+// Set a key-value pair with a particular timestamp.
+func (tm *TimeMap) Set(key, value interface{}, time int) {
+	tm.data[key] = append(tm.data[key], &TimestampedValue{time, value})
+	sort.Slice(tm.data[key], func(i, j int) bool {
+		return tm.data[key][i].Time < tm.data[key][j].Time
+	})
+}
+
+// Get returns the value for a key at a particular time.
+func (tm *TimeMap) Get(key interface{}, time int) interface{} {
+	pos := sort.Search(len(tm.data[key]), func(i int) bool {
+		return tm.data[key][i].Time > time
+	})
+	if pos <= 0 {
+		if len(tm.data[key]) == 0 || tm.data[key][0].Time > time {
+			return nil
+		}
+	}
+	return tm.data[key][pos-1].Value
+}


Test patch:
diff --git a/day97/problem_test.go b/day97/problem_test.go
new file mode 100644
index 0000000..ef083bf
--- /dev/null
+++ b/day97/problem_test.go
@@ -0,0 +1,50 @@
+package day97
+
+import "testing"
+
+func TestTimeMap(t *testing.T) {
+	t.Parallel()
+	d := NewTimeMap()
+	d.Set(1, 1, 0) // set key 1 to value 1 at time 0
+	d.Set(1, 2, 2) // set key 1 to value 2 at time 2
+	if result := d.Get(1, 1); result != 1 {
+		t.Errorf("get key 1 at time 1 should be 1")
+	}
+	if result := d.Get(1, 3); result != 2 {
+		t.Errorf("get key 1 at time 3 should be 2")
+	}
+	d.Set(1, 1, 5) // set key 1 to value 1 at time 5
+	if result := d.Get(1, 0); result != 1 {
+		t.Errorf("get key 1 at time 0 should be 1")
+	}
+	if result := d.Get(1, 10); result != 1 {
+		t.Errorf("get key 1 at time 10 should be 1")
+	}
+	d.Set(1, 1, 0) // set key 1 to value 1 at time 0
+	d.Set(1, 2, 0) // set key 1 to value 2 at time 0
+	if result := d.Get(1, 0); result != 2 {
+		t.Errorf("get key 1 at time 0 should be 2")
+	}
+	if result := d.Get(2, 0); result != nil {
+		t.Errorf("unused keys should return nil")
+	}
+	if result := d.Get(1, -1); result != nil {
+		t.Errorf("No value should be set back in time.")
+	}
+}
+
+func BenchmarkTimeMap(b *testing.B) {
+	d := NewTimeMap()
+	d.Set(1, 1, 0) // set key 1 to value 1 at time 0
+	d.Set(1, 2, 2) // set key 1 to value 2 at time 2
+	d.Set(1, 1, 5) // set key 1 to value 1 at time 5
+	for i := 0; i < b.N; i++ {
+		d.Get(1, 1)
+		d.Get(1, 3)
+		d.Get(1, 0)
+		d.Get(1, 10)
+		d.Get(1, 0)
+		d.Get(2, 0)
+		d.Get(1, -1)
+	}
+}