Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 235
Good morning! Here's your coding interview problem for today.

This problem was asked by Facebook.

Given an array of numbers of length N, find both the minimum and maximum using less than `2 * (N - 2)` comparisons.

Pull request:
Day235
Resolves #483.

Patch:
diff --git a/README.md b/README.md
index 574fc40..e21ffa5 100644
--- a/README.md
+++ b/README.md
@@ -243,3 +243,4 @@ problems from
 * [Day 232](https://github.com/vaskoz/dailycodingproblem-go/issues/477)
 * [Day 233](https://github.com/vaskoz/dailycodingproblem-go/issues/479)
 * [Day 234](https://github.com/vaskoz/dailycodingproblem-go/issues/481)
+* [Day 235](https://github.com/vaskoz/dailycodingproblem-go/issues/483)
diff --git a/day235/problem.go b/day235/problem.go
new file mode 100644
index 0000000..ca6657e
--- /dev/null
+++ b/day235/problem.go
@@ -0,0 +1,51 @@
+package day235
+
+// MaxMinNotGoodEnough returns the minimum and maximum values
+// from the slice of integers.
+// Runs in 2*(N-1) because it does N-1 comparisons for both
+// min and max.
+func MaxMinNotGoodEnough(nums []int) (min, max int) {
+	if len(nums) == 0 {
+		return 0, 0
+	}
+	min, max = nums[0], nums[0]
+	for i := 1; i < len(nums); i++ {
+		if nums[i] < min {
+			min = nums[i]
+		}
+		if nums[i] > max {
+			max = nums[i]
+		}
+	}
+	return min, max
+}
+
+// MaxMinPairs returns the minimum and maximum values
+// from the slice of integers.
+// Runs in 3N/2 which is smaller than 2*(N-2)
+func MaxMinPairs(nums []int) (min, max int) {
+	if len(nums) == 0 {
+		return 0, 0
+	} else if len(nums) == 1 {
+		return nums[0], nums[0]
+	}
+	min, max = nums[0], nums[1]
+	start := 2
+	if len(nums)%2 == 1 {
+		min, max = nums[0], nums[0]
+		start = 1
+	}
+	for i := start; i < len(nums); i += 2 {
+		ma, mi := nums[i], nums[i+1]
+		if mi > ma {
+			ma, mi = mi, ma
+		}
+		if ma > max {
+			max = ma
+		}
+		if mi < min {
+			min = mi
+		}
+	}
+	return min, max
+}


Test patch:
diff --git a/day235/problem_test.go b/day235/problem_test.go
new file mode 100644
index 0000000..28c7397
--- /dev/null
+++ b/day235/problem_test.go
@@ -0,0 +1,46 @@
+package day235
+
+import "testing"
+
+var testcases = []struct {
+	nums     []int
+	min, max int
+}{
+	{[]int{3, 3, 2, 3, 5, 6, 3, 2, 3, 3, 3, 2, -10, 323, 3, 3, 3, 35, 5, 6, 6, 6, 500, 23, 320, 320, 10}, -10, 500},
+	{nil, 0, 0},
+	{[]int{4}, 4, 4},
+}
+
+func TestMaxMinNotGoodEnough(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if min, max := MaxMinNotGoodEnough(tc.nums); min != tc.min || max != tc.max {
+			t.Errorf("Expected (%d,%d) got (%d,%d)", tc.min, tc.max, min, max)
+		}
+	}
+}
+
+func BenchmarkMaxMinNotGoodEnough(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaxMinNotGoodEnough(tc.nums)
+		}
+	}
+}
+
+func TestMaxMinPairs(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if min, max := MaxMinPairs(tc.nums); min != tc.min || max != tc.max {
+			t.Errorf("Expected (%d,%d) got (%d,%d)", tc.min, tc.max, min, max)
+		}
+	}
+}
+
+func BenchmarkMaxMinPairs(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaxMinPairs(tc.nums)
+		}
+	}
+}