Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 323
Good morning! Here's your coding interview problem for today.

This problem was asked by Dropbox.

Create an algorithm to efficiently compute the approximate median of a list of numbers.

More precisely, given an unordered list of `N` numbers, find an element whose rank is between `N / 4` and `3 * N / 4`, with a high level of certainty, in less than `O(N)` time.

Pull request description:
Day323
Resolves #656.

Patch:
diff --git a/README.md b/README.md
index b955c47..f6b7e26 100644
--- a/README.md
+++ b/README.md
@@ -326,3 +326,4 @@ problems from
 * [Day 320](https://github.com/vaskoz/dailycodingproblem-go/issues/650)
 * [Day 321](https://github.com/vaskoz/dailycodingproblem-go/issues/651)
 * [Day 322](https://github.com/vaskoz/dailycodingproblem-go/issues/654)
+* [Day 323](https://github.com/vaskoz/dailycodingproblem-go/issues/656)
diff --git a/day323/problem.go b/day323/problem.go
new file mode 100644
index 0000000..51ea354
--- /dev/null
+++ b/day323/problem.go
@@ -0,0 +1,31 @@
+package day323
+
+import (
+	"math/rand"
+	"sort"
+	"time"
+)
+
+// global but unexported for testing.
+// nolint
+var r = rand.New(rand.NewSource(time.Now().UnixNano()))
+
+// ApproximateMedian returns a value approximately close to
+// the real median.
+// Works by randomly sampling half (N/2) the input.
+// Runs in O(N/2) time and O(N/2) extra space.
+func ApproximateMedian(unordered []int) int {
+	size := len(unordered)
+	sampleSize := int(0.5 * float64(size))
+	picks := make(map[int]struct{}, sampleSize)
+	for len(picks) < sampleSize {
+		picks[r.Intn(size)] = struct{}{}
+	}
+	nums := make([]int, 0, len(picks))
+	for pick := range picks {
+		nums = append(nums, unordered[pick])
+	}
+	sort.Ints(nums)
+	mid := len(nums) / 2
+	return (nums[mid] + nums[mid+1]) / 2
+}


Test patch:
diff --git a/day323/problem_test.go b/day323/problem_test.go
new file mode 100644
index 0000000..b40fce1
--- /dev/null
+++ b/day323/problem_test.go
@@ -0,0 +1,33 @@
+package day323
+
+import (
+	"math/rand"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	unordered    []int
+	approxMedian int
+}{
+	{[]int{1, 10, 2, 9, 3, 8, 4, 7, 5, 6}, 7},
+	{[]int{10, 10, 10, 10, 10, 1, 1, 1, 1, 1}, 5},
+}
+
+func TestApproximateMedian(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		r = rand.New(rand.NewSource(42)) // fixed number for test determinism.
+		if median := ApproximateMedian(tc.unordered); median != tc.approxMedian {
+			t.Errorf("Expected %v, got %v", tc.approxMedian, median)
+		}
+	}
+}
+
+func BenchmarkApproximateMedian(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			ApproximateMedian(tc.unordered)
+		}
+	}
+}