Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 470
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given an array of numbers and an index `i`, return the index of the nearest larger number of the number at index `i`, where distance is measured in array indices.

For example, given `[4, 1, 3, 5, 6]` and index `0`, you should return `3`.

If two distances to larger numbers are the equal, then return any one of them. If the array at `i` doesn't have a nearest larger integer, then return `null`.

Follow-up: If you can preprocess the array, can you do this in constant time?

Pull request:
Day470
Resolves #945.

Patch:
diff --git a/README.md b/README.md
index 9bf95b7..c329da1 100644
--- a/README.md
+++ b/README.md
@@ -462,6 +462,7 @@ problems from
 * [Day 463](https://github.com/vaskoz/dailycodingproblem-go/issues/937)
 * [Day 464](https://github.com/vaskoz/dailycodingproblem-go/issues/935)
 * [Day 465](https://github.com/vaskoz/dailycodingproblem-go/issues/933)
+* [Day 470](https://github.com/vaskoz/dailycodingproblem-go/issues/945)
 * [Day 471](https://github.com/vaskoz/dailycodingproblem-go/issues/943)
 * [Day 472](https://github.com/vaskoz/dailycodingproblem-go/issues/941)
 * [Day 473](https://github.com/vaskoz/dailycodingproblem-go/issues/939)
diff --git a/day470/problem.go b/day470/problem.go
new file mode 100644
index 0000000..c441edd
--- /dev/null
+++ b/day470/problem.go
@@ -0,0 +1,39 @@
+package day470
+
+// ClosestLargerNumberIndexBrute looks for the closest number larger
+// than the target and returns the index of that number.
+// If no number if found, then -1 is returned.
+// Runs in O(N) time.
+func ClosestLargerNumberIndexBrute(nums []int, targetIndex int) int {
+	if targetIndex < 0 || targetIndex >= len(nums) {
+		panic("index out of bounds")
+	}
+
+	val := nums[targetIndex]
+	left, right := targetIndex-1, targetIndex+1
+
+	for left >= 0 || right < len(nums) {
+		if left >= 0 && nums[left] > val {
+			return left
+		} else if right < len(nums) && nums[right] > val {
+			return right
+		}
+		left--
+		right++
+	}
+
+	return -1
+}
+
+// PreprocessClosestLargerNumberIndex pre-processes the input and returns a new
+// slice that can answer the question for any index in O(1).
+// This pre-processing takes O(N^2) time.
+func PreprocessClosestLargerNumberIndex(nums []int) []int {
+	res := make([]int, len(nums))
+
+	for i := range nums {
+		res[i] = ClosestLargerNumberIndexBrute(nums, i)
+	}
+
+	return res
+}


Test patch:
diff --git a/day470/problem_test.go b/day470/problem_test.go
new file mode 100644
index 0000000..2b282c7
--- /dev/null
+++ b/day470/problem_test.go
@@ -0,0 +1,62 @@
+package day470
+
+import "testing"
+
+// nolint
+var testcases = []struct {
+	nums        []int
+	targetIndex int
+	expected    int
+}{
+	{[]int{4, 1, 3, 5, 6}, 0, 3},
+	{[]int{4, 1, 3, 5, 6}, 4, -1},
+	{[]int{4, 1, 3, 5, 6}, 1, 0},
+}
+
+func TestClosestLargerNumberIndexBrute(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if result := ClosestLargerNumberIndexBrute(tc.nums, tc.targetIndex); result != tc.expected {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func TestClosestLargerNumberIndexBruteBoundsCheck(t *testing.T) {
+	t.Parallel()
+
+	defer func() {
+		if err := recover(); err == nil {
+			t.Errorf("It should panic with an index out of bounds")
+		}
+	}()
+	ClosestLargerNumberIndexBrute([]int{1, 2}, 3)
+}
+
+func BenchmarkClosestLargerNumberIndexBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			ClosestLargerNumberIndexBrute(tc.nums, tc.targetIndex)
+		}
+	}
+}
+
+func TestPreprocessClosestLargerNumberIndex(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		pre := PreprocessClosestLargerNumberIndex(tc.nums)
+		if result := pre[tc.targetIndex]; result != tc.expected {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkPreprocessClosestLargerNumberIndex(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			PreprocessClosestLargerNumberIndex(tc.nums)
+		}
+	}
+}