Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 18
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given an array of integers and a number k, where 1 <= k <= length of the array, compute the maximum values of each subarray of length k.

For example, given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get: [10, 7, 8, 8], since:

10 = max(10, 5, 2)
7 = max(5, 2, 7)
8 = max(2, 7, 8)
8 = max(7, 8, 7)
Do this in O(n) time and O(k) space. You can modify the input array in-place and you do not need to store the results. You can simply print them out as you compute them.

Pull request description:
Day 18
Resolves #39 

Patch:
diff --git a/README.md b/README.md
index efdb947..f828aa3 100644
--- a/README.md
+++ b/README.md
@@ -28,3 +28,4 @@ problems from
 * [Day 15](https://github.com/vaskoz/dailycodingproblem-go/issues/33)
 * [Day 16](https://github.com/vaskoz/dailycodingproblem-go/issues/35)
 * [Day 17](https://github.com/vaskoz/dailycodingproblem-go/issues/37)
+* [Day 18](https://github.com/vaskoz/dailycodingproblem-go/issues/39)
diff --git a/day18/problem.go b/day18/problem.go
new file mode 100644
index 0000000..15816bb
--- /dev/null
+++ b/day18/problem.go
@@ -0,0 +1,35 @@
+package day18
+
+// MaxSubarraysBrute uses no extra memory, but runs in O(k*N)
+func MaxSubarraysBrute(nums []int, k int) []int {
+	var result []int
+	for i := 0; i < len(nums)-k+1; i++ {
+		max := nums[i]
+		for j := i + 1; j < i+k; j++ {
+			if nums[j] > max {
+				max = nums[j]
+			}
+		}
+		result = append(result, max)
+	}
+	return result
+}
+
+// MaxSubarraysOnePass runs through the input only once.
+func MaxSubarraysOnePass(nums []int, k int) []int {
+	var result []int
+	var sublist []int // O(k) extra space
+	for i := 0; i < len(nums); i++ {
+		if i >= k {
+			result = append(result, nums[sublist[0]])
+		}
+		for len(sublist) > 0 && sublist[0] <= i-k {
+			sublist = sublist[1:]
+		}
+		for len(sublist) > 0 && nums[i] >= nums[sublist[len(sublist)-1]] {
+			sublist = sublist[:len(sublist)-1]
+		}
+		sublist = append(sublist, i)
+	}
+	return append(result, nums[sublist[0]])
+}


Test patch:
diff --git a/day18/problem_test.go b/day18/problem_test.go
new file mode 100644
index 0000000..22a2a95
--- /dev/null
+++ b/day18/problem_test.go
@@ -0,0 +1,56 @@
+package day18
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	input    []int
+	k        int
+	expected []int
+}{
+	{[]int{10, 5, 2, 7, 8, 7}, 3, []int{10, 7, 8, 8}},
+	{[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
+		26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
+		51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75,
+		76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100},
+		25,
+		[]int{25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
+			51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75,
+			76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100}},
+}
+
+func TestMaxSubarraysBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MaxSubarraysBrute(tc.input, tc.k); !reflect.DeepEqual(tc.expected, result) {
+			t.Errorf("Expected %v bot got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkMaxSubarraysBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaxSubarraysBrute(tc.input, tc.k)
+		}
+	}
+}
+
+func TestMaxSubarraysOnePass(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MaxSubarraysOnePass(tc.input, tc.k); !reflect.DeepEqual(tc.expected, result) {
+			t.Errorf("Expected %v bot got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkMaxSubarraysOnePass(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MaxSubarraysOnePass(tc.input, tc.k)
+		}
+	}
+}