Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 377
Good morning! Here's your coding interview problem for today.

This problem was asked by Microsoft.

Given an array of numbers arr and a window of size `k`, print out the median of each window of size `k` starting from the left and moving right by one position each time.

For example, given the following array and `k = 3`:
```
[-1, 5, 13, 8, 2, 3, 3, 1]
```
Your function should print out the following:
```
5 <- median of [-1, 5, 13]
8 <- median of [5, 13, 8]
8 <- median of [13, 8, 2]
3 <- median of [8, 2, 3]
3 <- median of [2, 3, 3]
3 <- median of [3, 3, 1]
```
**Recall that the median of an even-sized list is the average of the two middle numbers.**

Pull request description:
Day377
Resolves #760.

Patch:
diff --git a/README.md b/README.md
index 216311c..376991b 100644
--- a/README.md
+++ b/README.md
@@ -372,4 +372,5 @@ problems from
 * [Day 374](https://github.com/vaskoz/dailycodingproblem-go/issues/754)
 * [Day 375](https://github.com/vaskoz/dailycodingproblem-go/issues/756)
 * [Day 376](https://github.com/vaskoz/dailycodingproblem-go/issues/758)
+* [Day 377](https://github.com/vaskoz/dailycodingproblem-go/issues/760)
 
diff --git a/day377/problem.go b/day377/problem.go
new file mode 100644
index 0000000..ffa2885
--- /dev/null
+++ b/day377/problem.go
@@ -0,0 +1,24 @@
+package day377
+
+import "sort"
+
+// BruteKMedians calculates the median of every k-sized
+// window using brute force.
+// It runs in O(N*K log K).
+func BruteKMedians(nums []float64, k int) []float64 {
+	ans := make([]float64, 0, len(nums)-k)
+	window := make([]float64, k)
+
+	for i := 0; i <= len(nums)-k; i++ {
+		copy(window, nums[i:k+i])
+		sort.Float64s(window)
+
+		if k%2 == 0 {
+			ans = append(ans, (window[k/2]+window[(k/2)-1])/2)
+		} else {
+			ans = append(ans, window[k/2])
+		}
+	}
+
+	return ans
+}


Test patch:
diff --git a/day377/problem_test.go b/day377/problem_test.go
new file mode 100644
index 0000000..f2b2748
--- /dev/null
+++ b/day377/problem_test.go
@@ -0,0 +1,42 @@
+package day377
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	input    []float64
+	k        int
+	expected []float64
+}{
+	{
+		[]float64{-1, 5, 13, 8, 2, 3, 3, 1},
+		3,
+		[]float64{5, 8, 8, 3, 3, 3},
+	},
+	{
+		[]float64{-1, 5, 13, 8, 2, 3, 3, 1},
+		4,
+		[]float64{6.5, 6.5, 5.5, 3, 2.5},
+	},
+}
+
+func TestBruteKMedians(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if result := BruteKMedians(tc.input, tc.k); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkBruteKMedians(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			BruteKMedians(tc.input, tc.k)
+		}
+	}
+}