Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 314
Good morning! Here's your coding interview problem for today.

This problem was asked by Spotify.

You are the technical director of WSPT radio, serving listeners nationwide. For simplicity's sake we can consider each listener to live along a horizontal line stretching from `0` (west) to `1000` (east).

Given a list of `N` listeners, and a list of `M` radio towers, each placed at various locations along this line, determine what the minimum broadcast range would have to be in order for each listener's home to be covered.

For example, suppose `listeners = [1, 5, 11, 20]`, and `towers = [4, 8, 15]`. In this case the minimum range would be `5`, since that would be required for the tower at position `15` to reach the listener at position `20`.

Pull request:
Day314
Resolves #640.

Patch:
diff --git a/README.md b/README.md
index 45a3dc7..74a3081 100644
--- a/README.md
+++ b/README.md
@@ -320,3 +320,4 @@ problems from
 * [Day 310](https://github.com/vaskoz/dailycodingproblem-go/issues/633)
 * [Day 311](https://github.com/vaskoz/dailycodingproblem-go/issues/635)
 * [Day 312](https://github.com/vaskoz/dailycodingproblem-go/issues/637)
+* [Day 314](https://github.com/vaskoz/dailycodingproblem-go/issues/640)
diff --git a/day314/problem.go b/day314/problem.go
new file mode 100644
index 0000000..938afe7
--- /dev/null
+++ b/day314/problem.go
@@ -0,0 +1,41 @@
+package day314
+
+import "sort"
+
+// MinimumTowerRange returns the minimum range of a tower to
+// cover all listeners.
+// Assumes listeners and towers are sorted in ascending order.
+// NOTE: This sorts these slices, if they're not already.
+// Runs in O(N) time and O(1) space.
+func MinimumTowerRange(listeners, towers []int) int {
+	if !sort.IntsAreSorted(listeners) {
+		sort.Ints(listeners)
+	}
+	if !sort.IntsAreSorted(towers) {
+		sort.Ints(towers)
+	}
+	var minRange int
+	towerIndex := 0
+	for _, listener := range listeners {
+		dist := abs(listener - towers[towerIndex])
+		for i := towerIndex; i < len(towers); i++ {
+			if d := abs(listener - towers[i]); d > dist {
+				break
+			} else {
+				towerIndex = i
+				dist = d
+			}
+		}
+		if dist > minRange {
+			minRange = dist
+		}
+	}
+	return minRange
+}
+
+func abs(a int) int {
+	if a < 0 {
+		return -a
+	}
+	return a
+}


Test patch:
diff --git a/day314/problem_test.go b/day314/problem_test.go
new file mode 100644
index 0000000..baf042a
--- /dev/null
+++ b/day314/problem_test.go
@@ -0,0 +1,33 @@
+package day314
+
+import (
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	listeners, towers []int
+	minRange          int
+}{
+	{[]int{1, 5, 11, 20}, []int{4, 8, 15}, 5},
+	{[]int{20, 5, 1, 11}, []int{15, 8, 4}, 5},
+	{[]int{1, 5, 11, 20}, []int{21}, 20},
+	{[]int{1, 5, 11, 20}, []int{0}, 20},
+}
+
+func TestMinimumTowerRange(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MinimumTowerRange(tc.listeners, tc.towers); result != tc.minRange {
+			t.Errorf("Expected %v, got %v", tc.minRange, result)
+		}
+	}
+}
+
+func BenchmarkMinimumTowerRange(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MinimumTowerRange(tc.listeners, tc.towers)
+		}
+	}
+}