CareerCup

can be solved using kd trees. Best case/Average case: O(lg n)...worst case: O(n)

Similar question was asked to me in amazon telephonic. Here is my solution,
Take first 3 nodes and build the max heap. heap contains the distance between the given point and the remaining points. Starting from next point, compute the distance to given point and compare the current distance with max element.. if it is greater than the max element then go to next element otherwise pop the max element and add this element.
In order to print the points, we can maintain a hash table (key=address to heap node, value = point(x,y))..
Any better solution?

It is possible in O(n^2). There are C(n,2) pairs involved. Calculate and cache the distance between each of them. Then for each point calculate the 3 min ditance in O(n) time.
Total time=O(n^2)+O(n)=O(n^2)

By using O(N) memory and yet another extension of algorithm mentioned
in Cormen (33.4), we can achieve an algorithm with O(NlogN) best case
and O(N^2) worst case.

Sort the vertices along x axis, ie sort points in increasing value of x coordinate. For each node maintain list of closest three points. After sorting do a horizontal scan of vertices. Once, the horizontal distance between two vertices becomes greater than furthest point of the vertex, it need not be part of further comparisons.

Ex, suppose points after sorting on x coordinate is , a,b,c,d,e,f,g. Scan this list. By the time we reach point f, if horizontal dist between ,say a and f is greater than the biggest of the three closest points to a, the vertex a need not be part of any further comparisons.

I think this will limit the number of comparisons,( worst case is still O ( n2) though ).

i've tested this one , assuming that the distance cannot be equal to Double.MAX_VALUE
=)
{{
public static void closest_points(Point[] points)
{
int[][] distances = new int[points.length][3];
for (int i=0; i<points.length; i++)
{
Point current_point = points[i];
Hashtable<Double, Integer> ht = new Hashtable<Double, Integer>();
double[] aux_distances = new double[points.length-1];
for (int j=0; j<points.length-1;j++)
{
if (i!=j){
double d = distance(current_point,points[j]);
aux_distances[j]=d;
if (d!=0)
ht.put(d,j);
} else
{
aux_distances[j]=Double.MAX_VALUE;
}
}
// print_array(aux_distances);
Arrays.sort(aux_distances);

for (int k=0; k<3; k++)
{
if (ht.get(aux_distances[k])!=null){
int index = (Integer)ht.get(aux_distances[k]);
distances[i][k] = index; }
}
}

for (int i=0; i< points.length; i++)
{
System.out.printf("%d ", i+1);
for (int j=0; j<3;j++){
System.out.printf(" %d ",distances[i][j]+1);
}
System.out.printf("\n");
}
}
}}

This is straightforward Java implementation with quadratic asymptotic runtime. I think this should be sufficient for an interview.

import java.util.*;

class ThreePointDistance
{
	static class Point
	{
		private double x;
		private double y;

		Point(double x, double y)
		{
			this.x = x;
			this.y = y;
		}

		// euclidean distance
		double distance(Point other)
		{
			double diffX = other.x - x;
			double diffY = other.y - y;

			return Math.sqrt(diffX*diffX + diffY*diffY);
		}
	}

	static class PointDist implements Comparable<PointDist>
	{
		private int pointIndex;
		private double dist;

		PointDist(int pointIndex, double dist)
		{
			this.pointIndex = pointIndex;
			this.dist = dist;
		}

		public int compareTo(PointDist other)
		{
			// descending order
			return (int) (other.dist - dist);
		}

		public double getDist() { return dist; }
		public int getPointindex() { return pointIndex; }
	}

	static void threeClosestPoints(Point[] points)
	{
		PriorityQueue<PointDist> pq = new PriorityQueue<>(3);
		PointDist[] closestPoints = new PointDist[3];
		for (int i=0; i < points.length; i++)
		{
			for (int j=0; j < points.length; j++)
			{
				if (i == j)
					continue;

				pq.offer(new PointDist(j, points[i].distance(points[j])));

				if (pq.size() > 3)
					pq.poll();
			}

			pq.toArray(closestPoints);
			Arrays.sort(closestPoints);
			
			System.out.println(String.format("%d: %d,%d,%d", i, closestPoints[2].getPointindex(),
																closestPoints[1].getPointindex(),
																closestPoints[0].getPointindex()));
			pq.clear();
		}
	}

	public static void main(String... args)
	{
		Point[] points = {new Point(0.0, 0.0), new Point(10.1, -10.1), new Point(-12.2, 12.2), new Point(38.3, 38.3), new Point(79.99, 179.99)};
		threeClosestPoints(points);
	}
}

Java implementation with distance based max-heap. Time complexity O(n^2).

private static List<List<Integer>> getPoints(Point[] points) {
    List<List<Integer>> res = new ArrayList<>();

    for (int i = 0; i < points.length; i++) {
        List<Integer> closestPoints = new ArrayList<>();
        Queue<PointWithId> queue =
                new PriorityQueue<>(3, new ClosestComparator(points[i]));

        for (int j=0; j<points.length; j++) {
            if (j==i) {
                continue;
            }
            queue.add(new PointWithId(points[j], j));
            if (queue.size() > 3) {
                queue.poll();
            }
        }

        while (!queue.isEmpty()) {
            closestPoints.add(queue.poll().id+1);
        }
        Collections.reverse(closestPoints);
        res.add(closestPoints);
    }
    return res;
}

static class Point {
    double x, y;

    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
}

static class PointWithId extends Point {
    int id;

    PointWithId(Point p, int id) {
        super(p.x, p.y);
        this.id = id;
    }
}

private static class ClosestComparator implements Comparator<Point> {

    private Point point;

    public ClosestComparator(Point point) {
        this.point = point;
    }

    @Override
    public int compare(Point p1, Point p2) {
        double d1 = Math.pow(Math.abs(point.x - p1.x), 2) +
                Math.pow(Math.abs(point.y - p1.y), 2);
        double d2 = Math.pow(Math.abs(point.x - p2.x), 2) +
                Math.pow(Math.abs(point.y - p2.y), 2);
        if (d1 == d2) {
            return 0;
        }
        return d1 > d2 ? -1 : 1;
    }
}

You can get O(n*logn) average time complexity with a kd-tree and its nearest-neighbour query. Good luck coding that on an interview. :)

First, sort along x-axis O(nlog(n))
Second, sort along y-axis O(nlog(n))
Third, find from nearest 6 (x and y) O(n)
Totally: O(nlog(n))