Day 340

[vaskoz]

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)].

[vaskoz]

Quickly did the brute force version in O(N^2): https://en.wikipedia.org/wiki/Closest_pair_of_points_problem#Brute-force_algorithm

There is an optimal O(N log N) solution as well.