Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 16
Good morning! Here's your coding interview problem for today.

This problem was asked by Twitter.

You run an e-commerce website and want to record the last N order ids in a log. Implement a data structure to accomplish this, with the following API:

record(order_id): adds the order_id to the log
get_last(i): gets the ith last element from the log. i is guaranteed to be smaller than or equal to N.
You should be as efficient with time and space as possible.

Pull request description:
Day16
Resolves #35.

Patch:
diff --git a/README.md b/README.md
index 90dc2b1..6992c6d 100644
--- a/README.md
+++ b/README.md
@@ -26,3 +26,4 @@ problems from
 * [Day 13](https://github.com/vaskoz/dailycodingproblem-go/issues/29)
 * [Day 14](https://github.com/vaskoz/dailycodingproblem-go/issues/31)
 * [Day 15](https://github.com/vaskoz/dailycodingproblem-go/issues/33)
+* [Day 16](https://github.com/vaskoz/dailycodingproblem-go/issues/35)
diff --git a/day16/problem.go b/day16/problem.go
new file mode 100644
index 0000000..cbde100
--- /dev/null
+++ b/day16/problem.go
@@ -0,0 +1,54 @@
+package day16
+
+import "container/ring"
+
+// OrderLog represents the behavior of an order log regardless of impl.
+type OrderLog interface {
+	Record(orderID interface{})
+	GetLast(index int) interface{}
+}
+
+type orderLogSlice struct {
+	log  []interface{}
+	pos  int
+	size int
+}
+
+// NewOrderLogSlice returns a new OrderLog based on a slice.
+func NewOrderLogSlice(size int) OrderLog {
+	return &orderLogSlice{log: make([]interface{}, size), pos: -1, size: size}
+}
+
+func (ol *orderLogSlice) Record(orderID interface{}) {
+	ol.pos++
+	if ol.pos >= ol.size {
+		ol.pos = 0
+	}
+	ol.log[ol.pos] = orderID
+}
+
+func (ol *orderLogSlice) GetLast(index int) interface{} {
+	i := ol.pos - (index - 1)
+	if i < 0 {
+		i += ol.size
+	}
+	return ol.log[i]
+}
+
+type orderLogRing struct {
+	log *ring.Ring
+}
+
+// NewOrderLogRing returns a new OrderLog based on a circular ring.
+func NewOrderLogRing(size int) OrderLog {
+	return &orderLogRing{ring.New(size)}
+}
+
+func (ol *orderLogRing) Record(orderID interface{}) {
+	ol.log = ol.log.Next()
+	ol.log.Value = orderID
+}
+
+func (ol *orderLogRing) GetLast(index int) interface{} {
+	return ol.log.Move(-(index - 1)).Value
+}


Test patch:
diff --git a/day16/problem_test.go b/day16/problem_test.go
new file mode 100644
index 0000000..e635d0b
--- /dev/null
+++ b/day16/problem_test.go
@@ -0,0 +1,75 @@
+package day16
+
+import "testing"
+
+var testcases = []struct {
+	size     int
+	orders   []interface{}
+	getLast  []int
+	expected []interface{}
+}{
+	{5, []interface{}{5, 4, "abc", 10, "def", "ged"},
+		[]int{1, 2, 3, 4, 5},
+		[]interface{}{"ged", "def", 10, "abc", 4}},
+	{5, []interface{}{"abc"},
+		[]int{1, 2, 3, 4, 5},
+		[]interface{}{"abc", nil, nil, nil, nil}},
+}
+
+func TestOrderLogSlice(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		r := NewOrderLogSlice(tc.size)
+		for _, v := range tc.orders {
+			r.Record(v)
+		}
+		for i, v := range tc.getLast {
+			if result := r.GetLast(v); result != tc.expected[i] {
+				t.Errorf("Expected %v but got %v", tc.expected[i], result)
+			}
+		}
+	}
+}
+
+func TestOrderLogRing(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		r := NewOrderLogRing(tc.size)
+		for _, v := range tc.orders {
+			r.Record(v)
+		}
+		for i, v := range tc.getLast {
+			if result := r.GetLast(v); result != tc.expected[i] {
+				t.Errorf("Expected %v but got %v", tc.expected[i], result)
+			}
+		}
+	}
+}
+
+func BenchmarkOrderLogSlice(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			r := NewOrderLogSlice(tc.size)
+			for _, v := range tc.orders {
+				r.Record(v)
+			}
+			for _, v := range tc.getLast {
+				r.GetLast(v)
+			}
+		}
+	}
+}
+
+func BenchmarkOrderLogRing(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			r := NewOrderLogRing(tc.size)
+			for _, v := range tc.orders {
+				r.Record(v)
+			}
+			for _, v := range tc.getLast {
+				r.GetLast(v)
+			}
+		}
+	}
+}