Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 150
Good morning! Here's your coding interview problem for today.

This problem was asked by LinkedIn.

Given a list of points, a central point, and an integer k, find the nearest k points from the central point.

For example, given the list of points `[(0, 0), (5, 4), (3, 1)]`, the central point `(1, 2)`, and `k = 2`, return `[(0, 0), (3, 1)]`.

Pull request:
Day150
Resolves #312.

Patch:
diff --git a/README.md b/README.md
index 0159c18..c3080e7 100644
--- a/README.md
+++ b/README.md
@@ -160,3 +160,4 @@ problems from
 * [Day 147](https://github.com/vaskoz/dailycodingproblem-go/issues/304)
 * [Day 148](https://github.com/vaskoz/dailycodingproblem-go/issues/309)
 * [Day 149](https://github.com/vaskoz/dailycodingproblem-go/issues/311)
+* [Day 150](https://github.com/vaskoz/dailycodingproblem-go/issues/312)
diff --git a/day150/problem.go b/day150/problem.go
new file mode 100644
index 0000000..b7d84df
--- /dev/null
+++ b/day150/problem.go
@@ -0,0 +1,64 @@
+package day150
+
+import (
+	"container/heap"
+	"math"
+)
+
+// Point has an X and Y coordinate.
+type Point struct {
+	X, Y int
+}
+
+type item struct {
+	dist float64
+	pt   Point
+}
+
+type priorityQueue []*item
+
+func (pq priorityQueue) Len() int { return len(pq) }
+
+func (pq priorityQueue) Less(i, j int) bool {
+	return pq[i].dist > pq[j].dist
+}
+
+func (pq priorityQueue) Swap(i, j int) {
+	pq[i], pq[j] = pq[j], pq[i]
+}
+
+func (pq *priorityQueue) Push(x interface{}) {
+	item := x.(*item)
+	*pq = append(*pq, item)
+}
+
+func (pq *priorityQueue) Pop() interface{} {
+	old := *pq
+	n := len(old)
+	item := old[n-1]
+	*pq = old[:n-1]
+	return item
+}
+
+// KNearestPoints returns the k-nearest points closest to a center point.
+// Runs in O(N log K) time.
+func KNearestPoints(pts []Point, center Point, k int) []Point {
+	pq := make(priorityQueue, 0, k)
+	for _, pt := range pts {
+		dist := math.Sqrt(
+			math.Pow(float64(pt.X-center.X), 2.0) +
+				math.Pow(float64(pt.Y-center.Y), 2.0))
+		if pq.Len() == k && dist < pq[0].dist {
+			heap.Pop(&pq)
+			heap.Push(&pq, &item{dist, pt})
+		} else if pq.Len() < k {
+			heap.Push(&pq, &item{dist, pt})
+		}
+	}
+	result := make([]Point, 0, k)
+	for pq.Len() > 0 {
+		it := heap.Pop(&pq).(*item)
+		result = append(result, it.pt)
+	}
+	return result
+}


Test patch:
diff --git a/day150/problem_test.go b/day150/problem_test.go
new file mode 100644
index 0000000..34f5acd
--- /dev/null
+++ b/day150/problem_test.go
@@ -0,0 +1,35 @@
+package day150
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	pts      []Point
+	center   Point
+	k        int
+	expected []Point
+}{
+	{[]Point{{0, 0}, {5, 4}, {3, 1}}, Point{1, 2}, 2, []Point{{0, 0}, {3, 1}}},
+	{[]Point{{5, 4}, {3, 1}, {0, 0}}, Point{1, 2}, 2, []Point{{3, 1}, {0, 0}}},
+	{[]Point{{5, 4}, {3, 1}, {0, 0}, {10, 10}, {20, 20}, {30, 30}}, Point{1, 2}, 2, []Point{{3, 1}, {0, 0}}},
+	{[]Point{{5, 4}, {0, 0}, {10, 10}, {20, 20}, {3, 1}, {30, 30}}, Point{1, 2}, 2, []Point{{0, 0}, {3, 1}}},
+}
+
+func TestKNearestPoints(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := KNearestPoints(tc.pts, tc.center, tc.k); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkKNearestPoints(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			KNearestPoints(tc.pts, tc.center, tc.k)
+		}
+	}
+}