CareerCup

just curious is this for java programming position? or c/c++?

was it a onsite or telephonic question ?

Can do this in several ways.
1. Sort all points by distance from given point and take first k - O(NlogN)
2. Use min heap of size k push all points there. Track the size of heap, remove the last element when size of heap is k+1. This will work at NlogK.

Nice Methods gevorgk!
How about using something like interval trees (augmented BST)?

function findKclosest(point x, point A[], int n)
{
    MAX-HEAP m = new MAX-HEAP(A[1...k])
    MAX = m.GetMax();

    for(c = k+1 to n)
    {
       if(Distance(A[c] < MAX) 
       {
           m.RemoveMax();
           m.Insert(new Node(A[c], distance(A[c], x));
           MAX = m.GetMax();
       }
    }
  
 m.Print();   
}

even though it's O(nlog k) in theory, it performs better in practice (depending upon the distribution of points) because I compare against a MAX variable instead of getting the MAX from heap every time.

Syntax error in if(Distance(A[c] < MAX) :)