CareerCup

I guess it is about employing K-Nearest Neighbors(KNN) algorithm to solve the problem.

I can be wrong, but it looks very similar to the clustering problem. This algorithm might be used here - en.wikipedia.org/wiki/K-means_clustering

Is it to find any k nearest stars or find k-nearest stars to a given star?
Also what is the distance metric to be used?
eg: Euclidean, Manhattan or any other.

using kd tree is best option for this..

1) Is it closest to earth or a given star ?
In this case, u can just use max-heap

2) Is it find k closest among the given stars ?
This will be more complex and u might need KD trees.

K-D Trees are best when it comes to coordinates.
We can find k nearest stars to a given star but not sure how to find k nearest stars when no star is given.

Use a max heap of k elements and add the stars based on the distance in 3D. You don't need to calculate the exact distance, just use this formula (x * x + y * y + z * z).

Try this if it is to find the k closest stars from a given coordinate.

public Star[] findKClosest (Star[] stars, Coordinate origin, int k) {
		PriorityQueue<Star> pqueue = PriorityQueue<Star> (k, new StarComperator());

		for (int i = 0; i < stars.length; i++) {
			int dist = dist(origin, starts[i].coord());

			if (pqueue.size() == k && pqeue.peek() > dist) {
				pqueue.pop();
			}

			pqueue.add(dist);
		}

		return pqueue.toArray(new Star [0]);
	}

An Amazon project manager(From Indian) asked me the same question in an interview.
Please note: 1 "huge set of stars as three dimensional coordinates" and 2 'k' has nothing to do with the distance by my understanding in the interview.
After the interview , I thought It might be have something with hash, because they always ask me 'hash this, hash that..' .
I had tried to use distance formula (x * x + y * y + z * z), but they said no. And even the closest
stars have a huge amount. I have no idea about K-Nearest Neighbors(KNN) and KD tree. But the question is how to deal with the huge amount stars by tree?