Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 201
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

You are given an array of arrays of integers, where each array corresponds to a row in a triangle of numbers. For example, `[[1], [2, 3], [1, 5, 1]]` represents the triangle:
```
  1
 2 3
1 5 1
```
We define a path in the triangle to start at the top and go down one row at a time to an adjacent value, eventually ending with an entry on the bottom row. For example, `1 -> 3 -> 5`. The weight of the path is the sum of the entries.

Write a program that returns the weight of the maximum weight path.

Pull request description:
Day201
Resolves #415.

Patch:
diff --git a/README.md b/README.md
index 4fbad7a..2974ac2 100644
--- a/README.md
+++ b/README.md
@@ -211,3 +211,4 @@ problems from
 * [Day 198](https://github.com/vaskoz/dailycodingproblem-go/issues/408)
 * [Day 199](https://github.com/vaskoz/dailycodingproblem-go/issues/409)
 * [Day 200](https://github.com/vaskoz/dailycodingproblem-go/issues/411)
+* [Day 201](https://github.com/vaskoz/dailycodingproblem-go/issues/415)
diff --git a/day201/problem.go b/day201/problem.go
new file mode 100644
index 0000000..da5209a
--- /dev/null
+++ b/day201/problem.go
@@ -0,0 +1,25 @@
+package day201
+
+// MaxWeightPathTriangle returns the weight of the maximum weight path
+// as defined by the problem.
+// Runs in O(N) time.
+// Assumes a correct triangle as input.
+func MaxWeightPathTriangle(tri [][]int) int {
+	return maxWeightPathTriangleHelper(tri, 0, 0)
+}
+
+func maxWeightPathTriangleHelper(tri [][]int, row, col int) int {
+	if row == len(tri)-1 {
+		return tri[row][col]
+	}
+	left := maxWeightPathTriangleHelper(tri, row+1, col)
+	right := maxWeightPathTriangleHelper(tri, row+1, col+1)
+	return tri[row][col] + max(left, right)
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/day201/problem_test.go b/day201/problem_test.go
new file mode 100644
index 0000000..67af1ca
--- /dev/null
+++ b/day201/problem_test.go
@@ -0,0 +1,27 @@
+package day201
+
+import "testing"
+
+var testcases = []struct {
+	triangle  [][]int
+	maxWeight int
+}{
+	{[][]int{{1}, {2, 3}, {1, 5, 1}}, 9},
+}
+
+func TestMaxWeightPathTriangle(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MaxWeightPathTriangle(tc.triangle); result != tc.maxWeight {
+			t.Errorf("Expected %v, got %v", tc.maxWeight, result)
+		}
+	}
+}
+
+func BenchmarkMaxWeightPathTriangle(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaxWeightPathTriangle(tc.triangle)
+		}
+	}
+}