Since this is an interview question, here is my shot at a solution. (As dcn points out below, this is not guaranteed to return the optimal solution, though it should still be a decent heuristic. Good catch, dcn!)
- Create a set Sp with a single point P.
- Compute the distance between every point in Sp and every point outside of it, then add the point with the smallest max distance to Sp.
- Repeat 2. until Sp has k points.
- Repeat 1-3 using each point once as the initial P. Take the Sp which has the smallest max distance.
There are O(k) points in Sp, and O(n) points outside of it, so finding the point with the smallest max distance is O(nk). We repeat this k times, then repeat the whole procedure n times, for an overall complexity of O(n2k2).
We can improve on this by caching the max distance between any point in Sp and each point outside of Sp. If maxDistanceFromPointInS[pointOutsideS]
is, say, an O(1) hash-table containing the current max distance between every point pointOutsideS
and some point inside Sp, then every time we add a new point newPoint
, we set maxDistanceFromPointInS[p] = Max(maxDistanceFromPointInS[p], distance(newPoint, p))
for all points p
outside of Sp. Then finding the smallest max distance is O(n), adding a point to Sp is O(n). Repeating this k times gives us O((n+n)k) = O(nk). Finally, we repeat the whole procedure n times, for an overall complexity of O(n2k).
We could improve finding the smallest max distance to O(1) using a heap, but that would not change the overall complexity.
By the way, it took an hour to write this all up - there's no way I could have done this in an interview.