Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 192
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

You are given an array of nonnegative integers. Let's say you start at the beginning of the array and are trying to advance to the end. You can advance at most, the number of steps that you're currently on. Determine whether you can get to the end of the array.

For example, given the array `[1, 3, 1, 2, 0, 1]`, we can go from indices `0 -> 1 -> 3 -> 5`, so return `true`.

Given the array `[1, 2, 1, 0, 0]`, we can't reach the end, so return `false`.

Pull request:
Day192
Resolves #397.

Patch:
diff --git a/README.md b/README.md
index c3633e6..a2e37e9 100644
--- a/README.md
+++ b/README.md
@@ -202,3 +202,4 @@ problems from
 * [Day 189](https://github.com/vaskoz/dailycodingproblem-go/issues/391)
 * [Day 190](https://github.com/vaskoz/dailycodingproblem-go/issues/393)
 * [Day 191](https://github.com/vaskoz/dailycodingproblem-go/issues/395)
+* [Day 192](https://github.com/vaskoz/dailycodingproblem-go/issues/397)
diff --git a/day192/problem.go b/day192/problem.go
new file mode 100644
index 0000000..3c08e9a
--- /dev/null
+++ b/day192/problem.go
@@ -0,0 +1,43 @@
+package day192
+
+// CanAdvanceToEndBrute tries to brute force the answer.
+func CanAdvanceToEndBrute(steps []int) bool {
+	if len(steps) < 2 {
+		return true
+	}
+	for step := 1; step <= steps[0] && step <= len(steps); step++ {
+		if CanAdvanceToEndBrute(steps[step:]) {
+			return true
+		}
+	}
+	return false
+}
+
+// CanAdvanceToEndLinear does it in one pass.
+func CanAdvanceToEndLinear(steps []int) bool {
+	if len(steps) < 2 {
+		return true
+	}
+	maxReach, step := steps[0], steps[0]
+	for i := 1; i < len(steps); i++ {
+		if i == len(steps)-1 {
+			return true
+		}
+		maxReach = max(maxReach, i+steps[i])
+		step--
+		if step == 0 {
+			if i >= maxReach {
+				break
+			}
+			step = maxReach - i
+		}
+	}
+	return false
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/day192/problem_test.go b/day192/problem_test.go
new file mode 100644
index 0000000..a67c43b
--- /dev/null
+++ b/day192/problem_test.go
@@ -0,0 +1,47 @@
+package day192
+
+import "testing"
+
+var testcases = []struct {
+	advanceFrom []int
+	possible    bool
+}{
+	{[]int{1, 3, 1, 2, 0, 1}, true},
+	{[]int{1, 2, 1, 0, 0}, false},
+	{[]int{0}, true},
+	{[]int{}, true},
+}
+
+func TestCanAdvanceToEndBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if possible := CanAdvanceToEndBrute(tc.advanceFrom); possible != tc.possible {
+			t.Errorf("Given %v, expected %v, got %v", tc.advanceFrom, tc.possible, possible)
+		}
+	}
+}
+
+func BenchmarkCanAdvanceToEndBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CanAdvanceToEndBrute(tc.advanceFrom)
+		}
+	}
+}
+
+func TestCanAdvanceToEndLinear(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if possible := CanAdvanceToEndLinear(tc.advanceFrom); possible != tc.possible {
+			t.Errorf("Given %v, expected %v, got %v", tc.advanceFrom, tc.possible, possible)
+		}
+	}
+}
+
+func BenchmarkCanAdvanceToEndLinear(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CanAdvanceToEndLinear(tc.advanceFrom)
+		}
+	}
+}