In a 3d space find points 10 points that are closest to the origin. Which data structure would you implement. What would be the time complexity of such a program.
I said that I would maintain 10 arrays that stores (x,y,z) coordinates and 10 int var to store the distance value.
int coordinates1[],value1,coordinates2[],value2,coordinates3[],value3....
We would start calculating Euclidean distance of the given point in hand and store it in those 10 arrays. As soon as we got 11th point we would replace it with the array corresponding to the highest value in the array.
As soon as we got the 12th point we would replace it with the 2nd highest corresponding value array ...after traversing through every point we would have the nearest 10 coordinates. I read this somewhere on career cup. I just modified the idea a little to accommodate 3d realm.
He asked what is space complexity. I said 10 arrays and 10 int values. A constant number will have a constant value n, O(n). He said fine, what if there are k points to be found. I said still it would be O(n). He said I was wrong it would be O(n square) since k points are inputted. I did not understand that part.
1. I think you can use Max Heap with K element to solve it easily, you just need maintain 10 element array, say:
- wave October 21, 2011Class Point
{
double x,y,z;
}
Point MaxHeap[k];
Complexity n*logk;