Adobe Interview Question
Software Engineer / DevelopersCountry: India
This can be solved using greedy approach. Generate a graph using points with the edge values as the distance between the vertices. Using min head data structure select the point with minimal edge cost and greedily select the other three points closest to the initial point. The cost is exponential.
I guess this belongs to computation geometry filed. if in 2D, find the smallest circle with 3 point on it. in 3D, find the smallest sphere with 4 points on its surface. something like Voronoi diagram and Delaunay triangulation could help?
I think the best approach here is to implement Kruskal's algorithm using Union-Find data structure and stop when a subtree has 4 points.
- Mihai February 21, 2013