Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 305
Good morning! Here's your coding interview problem for today.

This problem was asked by Amazon.

Given a linked list, remove all consecutive nodes that sum to zero. Print out the remaining nodes.

For example, suppose you are given the input `3 -> 4 -> -7 -> 5 -> -6 -> 6`. In this case, you should first remove `3 -> 4 -> -7`, then `-6 -> 6`, leaving only `5`.

Pull request description:
Day305
Resolves #622.

Patch:
diff --git a/README.md b/README.md
index 89aec29..951ef4d 100644
--- a/README.md
+++ b/README.md
@@ -311,3 +311,4 @@ problems from
 * [Day 302](https://github.com/vaskoz/dailycodingproblem-go/issues/615)
 * [Day 303](https://github.com/vaskoz/dailycodingproblem-go/issues/616)
 * [Day 304](https://github.com/vaskoz/dailycodingproblem-go/issues/618)
+* [Day 305](https://github.com/vaskoz/dailycodingproblem-go/issues/622)
diff --git a/day305/problem.go b/day305/problem.go
new file mode 100644
index 0000000..acbca9b
--- /dev/null
+++ b/day305/problem.go
@@ -0,0 +1,29 @@
+package day305
+
+// LL is a linked list of integers.
+type LL struct {
+	Value int
+	Next  *LL
+}
+
+// RemoveConsecutiveSumZero removes all sublists that sum to zero.
+// Runs in O(N^2) time and O(1) space.
+func RemoveConsecutiveSumZero(head *LL) *LL {
+	fakeHead := &LL{0, head}
+	for start := fakeHead; start != nil; start = start.Next {
+		var sum int
+		var farthest *LL
+		var found bool
+		for next := start.Next; next != nil; next = next.Next {
+			sum += next.Value
+			if sum == 0 {
+				farthest = next.Next
+				found = true
+			}
+		}
+		if found {
+			start.Next = farthest
+		}
+	}
+	return fakeHead.Next
+}


Test patch:
diff --git a/day305/problem_test.go b/day305/problem_test.go
new file mode 100644
index 0000000..48122d6
--- /dev/null
+++ b/day305/problem_test.go
@@ -0,0 +1,57 @@
+package day305
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	input, expected *LL
+}{
+	{
+		&LL{3, &LL{4, &LL{-7, &LL{5, &LL{-6, &LL{6, nil}}}}}},
+		&LL{5, nil},
+	},
+	{
+		&LL{3, &LL{4, &LL{5, &LL{-12, nil}}}},
+		nil,
+	},
+	{
+		&LL{3, &LL{4, &LL{-7, &LL{5, &LL{-5, &LL{6, nil}}}}}},
+		&LL{6, nil},
+	},
+	{
+		&LL{3, &LL{4, &LL{-7, &LL{3, &LL{5, &LL{-6, &LL{6, &LL{-5, nil}}}}}}}},
+		&LL{3, nil},
+	},
+	{
+		&LL{1, &LL{1, &LL{2, &LL{3, &LL{4, &LL{5, &LL{6, &LL{-5, nil}}}}}}}},
+		&LL{1, &LL{1, &LL{2, &LL{3, &LL{4, &LL{5, &LL{6, &LL{-5, nil}}}}}}}},
+	},
+}
+
+func equal(a, b *LL) bool {
+	for a != nil && b != nil {
+		if a.Value != b.Value {
+			return false
+		}
+		a = a.Next
+		b = b.Next
+	}
+	return a == nil && b == nil
+}
+
+func TestRemoveConsecutiveSumZero(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result := RemoveConsecutiveSumZero(tc.input); !equal(result, tc.expected) {
+			t.Errorf("TCID%d doesn't match", tcid)
+		}
+	}
+}
+
+func BenchmarkRemoveConsecutiveSumZero(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			RemoveConsecutiveSumZero(tc.input)
+		}
+	}
+}