Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 365
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

A quack is a data structure combining properties of both stacks and queues. It can be viewed as a list of elements written left to right such that three operations are possible:

* `push(x)`: add a new item `x` to the left end of the list
* `pop()`: remove and return the item on the left end of the list
* `pull()`: remove the item on the right end of the list.
Implement a quack using three stacks and `O(1)` additional memory, so that the amortized time for any push, pop, or pull operation is `O(1)`.

Pull request:
Day365
Resolves #720 and #721.

Patch:
diff --git a/README.md b/README.md
index f40a715..450c65a 100644
--- a/README.md
+++ b/README.md
@@ -346,3 +346,4 @@ problems from
 * [Day 362](https://github.com/vaskoz/dailycodingproblem-go/issues/714)
 * [Day 363](https://github.com/vaskoz/dailycodingproblem-go/issues/716)
 * [Day 364](https://github.com/vaskoz/dailycodingproblem-go/issues/718)
+* [Day 365](https://github.com/vaskoz/dailycodingproblem-go/issues/720)
diff --git a/day365/problem.go b/day365/problem.go
new file mode 100644
index 0000000..ea44c53
--- /dev/null
+++ b/day365/problem.go
@@ -0,0 +1,61 @@
+package day365
+
+import "errors"
+
+var errEmptyStack = errors.New("stack is empty")
+
+// ErrEmptyStack is the returned error for an empty stack.
+func ErrEmptyStack() error {
+	return errEmptyStack
+}
+
+// Quack is a data structure combining properties of both
+// stacks and queues.
+type Quack struct {
+	left, right, buffer []interface{}
+}
+
+// Push adds a new item x to the left end of the list.
+func (q *Quack) Push(x interface{}) {
+	q.left = append(q.left, x)
+}
+
+func (q *Quack) common(a, b *[]interface{}) (interface{}, error) {
+	if len(*a) == 0 && len(*b) == 0 {
+		return nil, errEmptyStack
+	}
+	if len(*a) == 0 {
+		for i := 0; i < len(*b)/2; i++ {
+			last := len(*b) - 1
+			x := (*b)[last]
+			*b = (*b)[:last]
+			q.buffer = append(q.buffer, x)
+		}
+		for len(*b) != 0 {
+			last := len(*b) - 1
+			x := (*b)[last]
+			*b = (*b)[:last]
+			*a = append(*a, x)
+		}
+		for len(q.buffer) != 0 {
+			last := len(q.buffer) - 1
+			x := q.buffer[last]
+			q.buffer = q.buffer[:last]
+			*b = append(*b, x)
+		}
+	}
+	last := len(*a) - 1
+	res := (*a)[last]
+	*a = (*a)[:last]
+	return res, nil
+}
+
+// Pop removes and return the item on the left end of the list.
+func (q *Quack) Pop() (interface{}, error) {
+	return q.common(&q.left, &q.right)
+}
+
+// Pull removes the item on the right end of the list.
+func (q *Quack) Pull() (interface{}, error) {
+	return q.common(&q.right, &q.left)
+}


Test patch:
diff --git a/day365/problem_test.go b/day365/problem_test.go
new file mode 100644
index 0000000..f26a0a5
--- /dev/null
+++ b/day365/problem_test.go
@@ -0,0 +1,92 @@
+package day365
+
+import "testing"
+
+type step struct {
+	action string
+	data   interface{}
+	err    error
+}
+
+// nolint
+var testcases = []struct {
+	steps []step
+}{
+	{
+		[]step{
+			{"push", "foo", nil},
+			{"push", "bcd", nil},
+			{"push", "def", nil},
+			{"pop", "def", nil},
+			{"pop", "bcd", nil},
+			{"pop", "foo", nil},
+			{"pop", nil, ErrEmptyStack()},
+			{"pull", nil, ErrEmptyStack()},
+		},
+	},
+	{
+		[]step{
+			{"push", "abc", nil},
+			{"push", "bcd", nil},
+			{"pull", "abc", nil},
+			{"push", "def", nil},
+			{"pop", "def", nil},
+			{"pop", "bcd", nil},
+		},
+	},
+	{
+		[]step{
+			{"push", "abc", nil},
+			{"push", "bcd", nil},
+			{"push", "def", nil},
+			{"push", "efg", nil},
+			{"push", "fgi", nil},
+			{"pull", "abc", nil},
+			{"pop", "fgi", nil},
+			{"pop", "efg", nil},
+			{"pop", "def", nil},
+			{"pop", "bcd", nil},
+			{"pull", nil, ErrEmptyStack()},
+			{"pop", nil, ErrEmptyStack()},
+		},
+	},
+}
+
+func TestQuack(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		q := &Quack{}
+		for _, s := range tc.steps {
+			switch s.action {
+			case "push":
+				q.Push(s.data)
+			case "pop":
+				if x, err := q.Pop(); x != s.data || err != s.err {
+					t.Errorf("Expected (%v,%v), got (%v,%v)", s.data, s.err, x, err)
+				}
+			case "pull":
+				if x, err := q.Pull(); x != s.data || err != s.err {
+					t.Errorf("Expected (%v,%v), got (%v,%v)", s.data, s.err, x, err)
+				}
+			}
+		}
+	}
+}
+
+func BenchmarkQuack(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			q := &Quack{}
+			for _, s := range tc.steps {
+				switch s.action {
+				case "push":
+					q.Push(s.data)
+				case "pop":
+					q.Pop() // nolint
+				case "pull":
+					q.Pull() // nolint
+				}
+			}
+		}
+	}
+}