Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 340
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given a set of points `(x, y)` on a 2D cartesian plane, find the two closest points. For example, given the points `[(1, 1), (-1, -1), (3, 4), (6, 1), (-1, -6), (-4, -3)]`, return `[(-1, -1), (1, 1)]`.

Pull request description:
Day340
Resolves #679.

Patch:
diff --git a/README.md b/README.md
index c4ca6c1..ceba8f4 100644
--- a/README.md
+++ b/README.md
@@ -330,3 +330,4 @@ problems from
 * [Day 324](https://github.com/vaskoz/dailycodingproblem-go/issues/658)
 * [Day 325](https://github.com/vaskoz/dailycodingproblem-go/issues/660)
 * [Day 339](https://github.com/vaskoz/dailycodingproblem-go/issues/676)
+* [Day 340](https://github.com/vaskoz/dailycodingproblem-go/issues/679)
diff --git a/day340/problem.go b/day340/problem.go
new file mode 100644
index 0000000..48ab266
--- /dev/null
+++ b/day340/problem.go
@@ -0,0 +1,34 @@
+package day340
+
+import "math"
+
+// Point is a 2D cartesian point.
+type Point struct {
+	X, Y int
+}
+
+// TwoClosestPointsBrute returns the two closest points.
+// It runs in O(N^2) time and O(1) extra space.
+// Just compares each point against the others.
+func TwoClosestPointsBrute(pts []Point) []Point {
+	if len(pts) < 2 {
+		return nil
+	} else if len(pts) == 2 {
+		return pts
+	}
+	res := make([]Point, 2)
+	dist := math.MaxFloat64
+	for i := 0; i < len(pts)-1; i++ {
+		for j := i + 1; j < len(pts); j++ {
+			d := math.Sqrt(
+				math.Pow(float64(pts[i].X-pts[j].X), 2.0) +
+					math.Pow(float64(pts[i].Y-pts[j].Y), 2.0))
+			if d < dist {
+				dist = d
+				res[0] = pts[i]
+				res[1] = pts[j]
+			}
+		}
+	}
+	return res
+}


Test patch:
diff --git a/day340/problem_test.go b/day340/problem_test.go
new file mode 100644
index 0000000..cde7e05
--- /dev/null
+++ b/day340/problem_test.go
@@ -0,0 +1,33 @@
+package day340
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	pts      []Point
+	expected []Point
+}{
+	{[]Point{}, nil},
+	{[]Point{{5, 10}, {20, 100}}, []Point{{5, 10}, {20, 100}}},
+	{[]Point{{1, 1}, {-1, -1}, {3, 4}, {6, 1}, {-1, -6}, {-4, -3}}, []Point{{1, 1}, {-1, -1}}},
+}
+
+func TestTwoClosestPointsBrute(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := TwoClosestPointsBrute(tc.pts); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected %v, got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkTwoClosestPointsBrute(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			TwoClosestPointsBrute(tc.pts)
+		}
+	}
+}