Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 141
Good morning! Here's your coding interview problem for today.

This problem was asked by Microsoft.

Implement 3 stacks using a single list:
```
class Stack:
    def __init__(self):
        self.list = []

    def pop(self, stack_number):
        pass

    def push(self, item, stack_number):
        pass
```

Pull request:
Day141
Resolves #294.

Patch:
diff --git a/README.md b/README.md
index 2ce9bd2..14a7aea 100644
--- a/README.md
+++ b/README.md
@@ -151,3 +151,4 @@ problems from
 * [Day 138](https://github.com/vaskoz/dailycodingproblem-go/issues/286)
 * [Day 139](https://github.com/vaskoz/dailycodingproblem-go/issues/288)
 * [Day 140](https://github.com/vaskoz/dailycodingproblem-go/issues/292)
+* [Day 141](https://github.com/vaskoz/dailycodingproblem-go/issues/294)
diff --git a/day141/problem.go b/day141/problem.go
new file mode 100644
index 0000000..fac598c
--- /dev/null
+++ b/day141/problem.go
@@ -0,0 +1,77 @@
+package day141
+
+import (
+	"errors"
+)
+
+type node struct {
+	value interface{}
+	prev  *node
+}
+
+// ThreeStacks represents 3-stacks
+// using only a single underlying list to store values.
+type ThreeStacks struct {
+	data         []*node
+	heads        [3]*node
+	pushes, pops int
+}
+
+// minDefrag represents the minimum number of Pops before
+// a defrag will happen.
+const minDefrag = 20
+
+var errInvalidStackID = errors.New("invalid stack id")
+var errEmptyStack = errors.New("stack is empty")
+
+// ErrInvalidStackID is returned if the stack id is not either 0, 1, 2.
+func ErrInvalidStackID() error {
+	return errInvalidStackID
+}
+
+// ErrEmptyStack is returned if the stack is empty.
+func ErrEmptyStack() error {
+	return errEmptyStack
+}
+
+// Pop removes and returns the most recent addition to the given
+// stack.
+func (ts *ThreeStacks) Pop(stackID int) (interface{}, error) {
+	if stackID < 0 || stackID >= 3 {
+		return nil, errInvalidStackID
+	}
+	if ts.heads[stackID] == nil {
+		return nil, errEmptyStack
+	}
+	ts.pops++
+	top := ts.heads[stackID]
+	ts.heads[stackID] = top.prev
+	if ts.pops > minDefrag {
+		defrag := make([]*node, 0, ts.pushes-ts.pops)
+		var pushes int
+		for i := 0; i < 3; i++ {
+			ptr := ts.heads[i]
+			for ptr != nil {
+				defrag = append(defrag, ptr)
+				pushes++
+				ptr = ptr.prev
+			}
+		}
+		ts.data = defrag
+		ts.pops = 0
+		ts.pushes = pushes
+	}
+	return top.value, nil
+}
+
+// Push adds the Value to the top of the given stack.
+func (ts *ThreeStacks) Push(val interface{}, stackID int) error {
+	if stackID < 0 || stackID > 2 {
+		return errInvalidStackID
+	}
+	ts.pushes++
+	v := &node{value: val, prev: ts.heads[stackID]}
+	ts.data = append(ts.data, v)
+	ts.heads[stackID] = v
+	return nil
+}


Test patch:
diff --git a/day141/problem_test.go b/day141/problem_test.go
new file mode 100644
index 0000000..0414be8
--- /dev/null
+++ b/day141/problem_test.go
@@ -0,0 +1,60 @@
+package day141
+
+import (
+	"testing"
+)
+
+func TestThreeStacks(t *testing.T) {
+	t.Parallel()
+	var stack ThreeStacks
+	for i := 0; i < 100; i++ {
+		stack.Push(i, i%3)
+	}
+	for i := 99; i >= 0; i-- {
+		if v, err := stack.Pop(i % 3); err != nil || v != i {
+			t.Errorf("Expected (%v,nil) got (%v,%v)", i, v, err)
+		}
+	}
+}
+
+func TestThreeStacksErrors(t *testing.T) {
+	t.Parallel()
+	var stack ThreeStacks
+
+	if err := stack.Push("foobar", 3); err != ErrInvalidStackID() {
+		t.Errorf("Expected an invalid stack id error for Push")
+	}
+	if _, err := stack.Pop(-1); err != ErrInvalidStackID() {
+		t.Errorf("Expected an invalid stack id error for Pop")
+	}
+	if _, err := stack.Pop(0); err != ErrEmptyStack() {
+		t.Errorf("Expected an empty stack error for Pop")
+	}
+}
+
+func TestThreeStacksDefrag(t *testing.T) {
+	t.Parallel()
+	var stack ThreeStacks
+	for i := 0; i < 100; i++ {
+		stack.Push(i, i%3)
+	}
+	for i := 99; i >= 0; i-- {
+		stack.Pop(i % 3)
+	}
+	if len(stack.data) > 20 {
+		t.Errorf("The list should have reduced due to defrag")
+	}
+}
+
+func BenchmarkThreeStacks(b *testing.B) {
+	var stack ThreeStacks
+	for i := 0; i < 10000; i++ {
+		stack.Push(i, i%3)
+	}
+	for i := 0; i < b.N; i++ {
+		stack.Push(i, i%3)
+		for j := 0; j < 30; j++ {
+			stack.Pop(j % 3)
+		}
+	}
+}