Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 180
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given a stack of N elements, interleave the first half of the stack with the second half reversed using only one other queue. This should be done in-place.

Recall that you can only push or pop from a stack, and enqueue or dequeue from a queue.

For example, if the stack is `[1, 2, 3, 4, 5]`, it should become `[1, 5, 2, 4, 3]`. If the stack is `[1, 2, 3, 4]`, it should become `[1, 4, 2, 3]`.

Hint: Try working backwards from the end state.

Pull request:
Day180
Resolves #373.

Patch:
diff --git a/README.md b/README.md
index ebf0a1e..458c781 100644
--- a/README.md
+++ b/README.md
@@ -190,3 +190,4 @@ problems from
 * [Day 177](https://github.com/vaskoz/dailycodingproblem-go/issues/365)
 * [Day 178](https://github.com/vaskoz/dailycodingproblem-go/issues/367)
 * [Day 179](https://github.com/vaskoz/dailycodingproblem-go/issues/371)
+* [Day 180](https://github.com/vaskoz/dailycodingproblem-go/issues/373)
diff --git a/day180/problem.go b/day180/problem.go
new file mode 100644
index 0000000..b74da14
--- /dev/null
+++ b/day180/problem.go
@@ -0,0 +1,61 @@
+package day180
+
+// Stack is a stack with only push & pop operations.
+type Stack struct {
+	data []interface{}
+}
+
+// Push adds an element to the stack.
+func (s *Stack) Push(v interface{}) {
+	s.data = append(s.data, v)
+}
+
+// Pop removes and element from the stack.
+func (s *Stack) Pop() interface{} {
+	var v interface{}
+	v, s.data = s.data[len(s.data)-1], s.data[:len(s.data)-1]
+	return v
+}
+
+// Len returns the number of items in the stack.
+func (s *Stack) Len() int {
+	return len(s.data)
+}
+
+// Queue is a simple FIFO queue.
+type Queue struct {
+	data []interface{}
+}
+
+// Enqueue adds to the queue.
+func (q *Queue) Enqueue(v interface{}) {
+	q.data = append(q.data, v)
+}
+
+// Dequeue removes an element from the queue.
+func (q *Queue) Dequeue() interface{} {
+	var v interface{}
+	v, q.data = q.data[0], q.data[1:]
+	return v
+}
+
+// Len returns the number of items in the queue.
+func (q *Queue) Len() int {
+	return len(q.data)
+}
+
+// InterleaveStack interleaves the first half of the stack
+// with the reverse of the second half.
+// This modifies the stack in place.
+// Uses only a queue for additional help.
+func InterleaveStack(s Stack) {
+	var q Queue
+	for cycles := s.Len() - 1; cycles > 0; cycles-- {
+		for i := 0; i < cycles; i++ {
+			q.Enqueue(s.Pop())
+		}
+		for q.Len() != 0 {
+			s.Push(q.Dequeue())
+		}
+	}
+}


Test patch:
diff --git a/day180/problem_test.go b/day180/problem_test.go
new file mode 100644
index 0000000..6631ad0
--- /dev/null
+++ b/day180/problem_test.go
@@ -0,0 +1,41 @@
+package day180
+
+import "testing"
+
+var testcases = []struct {
+	input, expected []interface{}
+}{
+	{[]interface{}{1, 2, 3, 4, 5}, []interface{}{1, 5, 2, 4, 3}},
+	{[]interface{}{1, 2, 3, 4}, []interface{}{1, 4, 2, 3}},
+	{[]interface{}{}, []interface{}{}},
+	{nil, nil},
+}
+
+func TestInterleaveStack(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		var s Stack
+		for _, v := range tc.input {
+			s.Push(v)
+		}
+		InterleaveStack(s)
+		for i := range tc.expected {
+			v := tc.expected[len(tc.expected)-1-i]
+			if result := s.Pop(); result != v {
+				t.Errorf("Expected (%v) got (%v)", v, result)
+			}
+		}
+	}
+}
+
+func BenchmarkInterleaveStack(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			var s Stack
+			for _, v := range tc.input {
+				s.Push(v)
+			}
+			InterleaveStack(s)
+		}
+	}
+}