CareerCup

You can do it in O(n), but you have to avoid heaps.
First build an array with the distances to the origin and the corresponding point. O(n)
Then find the Kth largest distance using the Selection algorithm. O(n)
The K-1 smallest distances are to the left of the Kth distance, in no particular order.

So the total is O(n).

Not elegant, but it works. (Java) Could probably make the code more elegant with more time.

//test the code
	public static void main(String[] args) {
		Vect2[] points = {new Vect2(1, 1),new Vect2(2, 2),new Vect2(3, 2),new Vect2(0, 1),new Vect2(1, 0)};
		Vect2[] points2 = getKclosest(points, 3);
		for (int i = 0; i < points2.length; i++) {
			System.out.println("point: "+points2[i]);
		}
	}
	
	
	public static Vect2[] getKclosest(Vect2[] points, int k) {
		//ArrayList<VectData> list = new ArrayList<VectData>(points.length);
		VectData[] list = new VectData[points.length];
		
		for (int i = 0, len = points.length; i < len; i++) {
			list[i]= new VectData(points[i]);}
		
		Arrays.sort(list);
		
		Vect2[] points2 = new Vect2[k];
		for (int i = 0; i < k; i++) {
			points2[i] = list[i].getVect();
		}
		return points2;
	}
	
	
 
	public static class VectData implements Comparable<VectData>{
		private Vect2 vect;
		private float dist2;//distance squared
		
		public float getDist2() {
			return dist2;}
		
		public Vect2 getVect(){
			return vect;}
		
		public VectData (Vect2 vect) {
			this.vect = vect;
			dist2 = dist2FromZero(vect);
		}
		
		public float dist2FromZero(Vect2 vect) {//we only need the squared-distance.  Less calc.
			return vect.x*vect.x+vect.y*vect.y;
		}

		@Override
		public int compareTo(VectData o) {
			return (o.getDist2() < this.getDist2())?1:-1;
		}
	}
	
	public static  class Vect2 {
		public float x;
		public float y;
		public Vect2(float x,float y){
			this.x=x; this.y=y;}
		
		@Override public String toString() {
			return "["+x+","+y+"]";
		}
		
	}

First idea could be: calculate all the distances in an array, sort the array,
then get the k smallest values from there. This would work fine, but as the
fastest sorting algorigthms are O(nlog(n)), there is a faster, O(n) solution.

While iterating over the array you fill a max-heap of length k with new values.

The exact implementation of the heap was not asked.

In PHP:

<?php
    class PointMaxHeap {
        // Creates the class and limits it to a certain size
        function __construct($size);
        // Adds a new value in the heap and removes the max value if new size
        // is bigger than the size it was initialized with
        function add($value, $point);
        // Returns the max current value
        function getMax();
        // Returns the current size of the heap
        function getSize();
        // Returns all current points
        function getPoints();
    }

    class Point {
        public $x;
        public $y;

        // Returns the Euclidian distance to origin
        function getDistanceFromOrigin() {
            return sqrt($this->x * $this->x + $this->y * $this->y);
        }
    }

    function getKClosest($points, $k) {
        $heap = new PointMaxHeap($k);

        foreach ($poitns as $point) {
            $d = $point->getDistanceFromOrigin();

            // If the heap isn't full yet, we just directly add the value
            // If the heap is full, but this point is closer to origin than
            // one of the points currently in the heap, we add the value
            if ($heap->getSize() < $k || $heap->getMax() > $d) {
                $heap->add($d, $point);
            }
        }

        return $heap->getPoints();
    }

int i =0;
HashMap map;
while(i<k){
  maxHeap.insert( xi^2 +yi^2 );
  map.put(xi^2 +yi^2, i);
  i++;
}
while(i<n){
  a =  xi^2 +yi^2 ; 
  if( a< maxElemetOfHeap){
	maxHeaaap.remove(maxElemetOfHeap);
	map.remove(maxElemetOfHeap);
	maxHeap.insert(a)
	map.put(a,i);
  }
}

iterate map

My thoughts:

1) Never use distance, but rather use the square on distance.
We don't want to get caught up in the ugliness of sqrt.

2) We can do this in place (and in most apps. this should be allowed because the set of points is just a "bag" of points):

3) Modify QuickSelect or MedianOfMedians to use a distance^2 comparison function "on the fly" on the original array itself.
This gets the k closest points into the first k elements of _original_ array of points.

Should be O(n)

Am I crazy but can't we do a BFS search on the 2D plane with a K count. Once K has hit its value we just return a list of found points? Here is the code:

static boolean inbounds(int[][] plane, int x, int y) {
        if (x >= 0 && y >= 0 && 
            x < plane[0].length && y < plane.length) {
            return true;
        }
        return false;
    }
    
    static int[][] closestk(int[][] plane, int k) {
        Queue<int[]> q = new ArrayDeque<int[]>();
        int[][] found = new int[k][2];
        int n=0;
        int x=0;
        int y=0;
        q.add(new int[]{x, y});
        while (!q.isEmpty()) {
            int[] tup = q.remove();
            int tmpx = tup[0];
            int tmpy = tup[1];
            int e = plane[tmpy][tmpx];
            if (e == 1) {
                found[n++] = tup;
            } if (n == k) {
                return found;
            }
            // NOTE: The order of the following 3
            // if statements are crutial. The diagnol
            // square is the "farthest" from our current point
            if (inbounds(plane, x+1, y)) {
                q.add(new int[]{x+1, y});
            }
            if (inbounds(plane, x, y+1)) {
                q.add(new int[]{x, y+1});
            }
            if (inbounds(plane, x+1, y+1)) {
                q.add(new int[]{x+1, y+1});
            }
            x++;
            y++;
        }
        return found;
    }

from random import random as rand

def knth(sample, n):
  pivot = sample[0]
  below = [s for s in sample if s < pivot]
  above = [s for s in sample if s > pivot]
  i, j = len(below), len(sample)-len(above)
  if n < i:      return knth(below, n)
  elif n >= j:   return knth(above, n-j)
  else:          return pivot

def kmindist(sample, n):
  distsquared = [x**2+y**2 for x,y in sample]
  last_element = knth(distsquared, n)
  return [d for d in distsquared if d < last_element]

def main():
  # Tester
  sample = [(rand(),rand()) for i in range(20)]
  print sample
  print kmindist(sample, 5)

if __name__ == "__main__":
  main()

But Like to know, when there are utility methods to sort still Interview expect to write a fresh sort?
Running code sample below with Two possible ways to solve this:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.Random;
import java.util.TreeMap;




public class PuzzleRunner {



public static void main(String[] args) {
try {
Plane2D plane2d = new PuzzleRunner().new Plane2D(10,5);
plane2d.fillRandomPoints(10);
plane2d.showGenetatedPoints();
System.out.println("Result by n log(n) performance" + plane2d.getClosedPoint());
System.out.println("guaranteed log(n) time cost" +plane2d.getClosedPoint2());

} catch (Exception e) {
System.out.println(e.getMessage());
}

}


protected class Plane2D {


private int length;
private int breath;
private ArrayList<Point> points;

Plane2D(int length, int breath) throws Exception{
if(length <= 0 || breath <= 0){
throw new Exception("Size is less then zeros not allowed in this version");
}
this.length = length;
this.breath = breath;

}

public void fillRandomPoints(int numberOfPoints){
points = new ArrayList<Point>(numberOfPoints);
Random randomX = new Random();
Random randomY = new Random();
for (int i = 0; i < numberOfPoints; i++) {
points.add(new Point(randomX.nextInt(length), randomY.nextInt(breath)));
}

}

public Point getClosedPoint(){
/**
* The sorting algorithm is a modified merge sort
* This algorithm offers guaranteed n log(n) performance
*/
Collections.sort(points);
return points.get(0);
}

public Point getClosedPoint2(){

//This implementation provides guaranteed log(n) time cost for the containsKey
TreeMap<Double, Point> treeMap = new TreeMap<Double, Point>();
for (Point point : points) {
treeMap.put(point.getDistanceOfPointsFromOrigin(), point);
}
return treeMap.get(treeMap.firstKey());
}

public void showGenetatedPoints(){

for (Iterator<Point> iterator = points.iterator(); iterator.hasNext();) {
Point point = (Point) iterator.next();
System.out.println(point);

}
}



}

protected class Point implements Comparable<Point> {

private double x;
private double y;
private double distanceOfPointsFromOrigin;

Point(double x, double y){
this.x = x;
this.y = y;
this.distanceOfPointsFromOrigin = Math.sqrt(getX()*getX() + getY()*getY());
}


public double getX() {
return x;
}

public double getY() {
return y;
}

@Override
public int compareTo(Point o) {
if(this.distanceOfPointsFromOrigin < o.getDistanceOfPointsFromOrigin()){
return -1;
}else if (this.distanceOfPointsFromOrigin > o.getDistanceOfPointsFromOrigin()){
return 1;
}else{
return 0;
}
}


@Override
public String toString() {
return "Point [x=" + x + ", y=" + y + "]";
}


public double getDistanceOfPointsFromOrigin() {
return distanceOfPointsFromOrigin;
}







}


}

//Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Point{
private float x;
private float y;
private Float distFrmOrig;

Point(float xaxis, float yaxis){
x=xaxis;
y=yaxis;
distFrmOrig=(x*x)+(y*y);
}
public float getX() {
return x;
}
public void setX(float x) {
this.x = x;
}
public float getY() {
return y;
}
public void setY(Float y) {
this.y = y;
}
public Float getDistFrmOrig() {
return distFrmOrig;
}
public void setDistFrmOrig(Float distFrmOrig) {
this.distFrmOrig = distFrmOrig;
}

}

public class KPointAlgo {

public static void main(String[] args){

List<Point>pointList=new ArrayList<Point>();
pointList.add(new Point(2,2));
pointList.add(new Point(3,3));
pointList.add(new Point(4,4));
pointList.add(new Point(5,5));
pointList.add(new Point(6,6));
pointList.add(new Point(7,7));
pointList.add(new Point(8,8));
pointList.add(new Point(9,9));
pointList.add(new Point(10,10));

//Let K =5
int k=5;
List<Point> KpointList= getKpointClosetoOrigin(pointList,k);
if(KpointList!=null){
for(Point point:KpointList){
System.out.println("X axis: " + point.getX()+" Y axis: "+ point.getY()+" and distance from origin is "+ point.getDistFrmOrig());
}
}

}

private static List<Point> getKpointClosetoOrigin(List<Point> pointList,
int k) {
if(pointList!=null && pointList.size()>0){
Collections.sort(pointList,new Comparator<Point>(){
@Override
public int compare(Point o1, Point o2) {
return o1.getDistFrmOrig().compareTo(o2.getDistFrmOrig());
}
});
return pointList.subList(0,k);
}

return null;
}

}

Updated solution.

This one is designed for practical use. In a typical scenario, I would expect to be given a very large number of points (i.e. 10,000,000) to search through & only a small number of k-points (i.e. 15 or less) that need to be returned.

Storing 10-million pointers and their distance values, or 'cheating' by having a point class that stores it's distance from (0,0) (what?!) would be extremely inefficient. Instead, we just store the k-closest points so far, and their distances.

As far as calculations, we save by using distance-squared and storing those distances.

For fun, I ran a test on my old laptop with 10-million random points and 15-closest, and the results returned in 125ms.

// test the code
	public static void main(String[] args) {
		Vect2[] points = randPts(25, 10f);
		Vect2[] points2 = vectDistSorter(5, new Vect2(0, 0), points);
		System.out.println("Starting Points");  //print results
		for (Vect2 point : points) {
			System.out.println("point: " + point);}
		System.out.println("===============");
		System.out.println("Results");
		for (Vect2 point : points2) {
			System.out.println("point: " + point);}
	}

	//generate test points
	public static Vect2[] randPts(int total, float scalar) {
		Vect2[] points = new Vect2[total];
		for (int i = 0; i < total; i++) {
			points[i] = new Vect2((float) Math.random() * scalar,
					(float) Math.random() * scalar);
		}
		return points;
	}

	/**
	 * Returns the closest K-points to the targetPt, from points array. Uses
	 * O(k) memory and worst case is O(points*k). This solution is ideal for a
	 * large number of points (i.e. 10000000) and a small number of k-closest
	 * (i.e. 10).
	 */
	public static Vect2[] vectDistSorter(int kClosest, Vect2 targetPt,Vect2[] points) {
		VectSortData vData = new VectSortData();
		vData.vect = new Vect2[kClosest];
		vData.dist2 = new float[kClosest];
		vData.totalPts = kClosest;
		vData.targetPt = targetPt;

		if (kClosest >= points.length) {
			return points;
		}// done early, that was easy!

		for (int i = 0; i < kClosest; i++) {// add first k points
			vData.vect[i] = points[i];
			vData.dist2[i] = vData.dist2FromPt(points[i]);
		}

		vData.selectNextMax();

		float curDist;
		for (int i = kClosest, len = points.length; i < len; i++) {// if closer,
																	// replace
																	// farthest
																	// point
			curDist = vData.dist2FromPt(points[i]);
			if (curDist < vData.curMaxDist) {
				vData.vect[vData.curMaxIndex] = points[i];// replace max pt
				vData.dist2[vData.curMaxIndex] = curDist;// replace distance
				vData.selectNextMax();// selext new farthest point
			}
		}

		return vData.vect;
	}
	
	// helper class that stores temporary closest-point data & does a couple opperations
	static class VectSortData {
		Vect2 vect[];// stores points
		float dist2[];// stores distance-squared
		Vect2 targetPt;// oritionating point
		int totalPts;// number of closest points
		float curMaxDist = 0;// distance of farthest point in our current list
		int curMaxIndex = 0;// cursor of current max. Saves searches

		float xDist;// less garbage collection
		float yDist;// less garbage collection

		// we only need the squared-distance.
		float dist2FromPt(Vect2 vect) {
			xDist = (vect.x - targetPt.x);
			yDist = (vect.y - targetPt.y);
			return xDist * xDist + yDist * yDist;
		}

		//searches for the next max-distance point & stores the distance and index
		void selectNextMax() {
			curMaxDist = 0;
			for (int i = 0; i < totalPts; i++) {
				if (dist2[i] > curMaxDist) {
					curMaxDist = dist2[i];
					curMaxIndex = i;
				}
			}
		}
	}

	// We need a points class to contain the points.
	public static class Vect2 {
		public float x;
		public float y;

		public Vect2(float x, float y) {
			this.x = x;
			this.y = y;
		}

		@Override public String toString() {return "[" + x + "," + y + "]";}
	}

@JonG
collabedit.com/4k9d4

Add and fix things in there as you please.

// k-closest-points-to-origin.cpp : Defines the entry point for the console application.
//

#include<iostream>
#include<algorithm>
using namespace std;
struct point{
int x,y;
};
point p[10];

int Dist(int i)
{
return p[i].x*p[i].x + p[i].y*p[i].y;
}

int partition(int low, int high,int mid)
{
int lookat=low;
int midr = Dist(mid);
while(lookat<=high)
{
int loDtr = Dist(lookat);
if(loDtr < midr)
{
swap(p[lookat],p[low]);
lookat++;low++;
}
if(loDtr > midr)
{
swap(p[lookat],p[high]);
high--;
}
else
lookat++;
}
return low;
}

void quickSelect(int k, int low, int high)
{
int mid = (low+high)/2;
int index = partition(low,high,mid);
int len = index-low+1;
if(k == len)
return;
else if (k < len)
quickSelect(k,low,index-1);
else
quickSelect(k-len,index+1,high);


}
int main()
{
for(int i=0;i<10;i++)
{
p[i].x = rand()%10;
p[i].y = rand()%10;
}

for(int i=0;i<10;i++)
{
cout<<p[i].x<<" "<<p[i].y<<endl;
}
cout<<endl;
quickSelect(5,0,9);

for(int i=0;i<10;i++)
{
cout<<p[i].x<<" "<<p[i].y<<endl;
}
getchar();
}

3 step operation: (1) calculate distances for all Points; (2) sort; (3) select K points closest to origin

public void FindClosestKPoints() {
		int nPoints = Math.max(1,(int) (Math.random()*100) );
		int k = Math.max(1, (int) (Math.random()*nPoints) );
		int[] distances = new int[nPoints], sortedList = new int[nPoints];
		Point[] pointsList2 = new Point[nPoints];

		for (int i=0; i<nPoints; i++) {  // Populate arrays
			pointsList2[i] = new Point((int) (Math.random()*100), (int) (Math.random()*100));
			sortedList[i] = distances[i] = distance(pointsList2[i]);
		}  //ENDFOR
		
		Arrays.sort(sortedList);  //Sort distance values
		System.out.println(String.format("----closest %s of %s Points. (dividing line=%s)-----", k, nPoints, sortedList[k-1]));
		System.out.println(String.format("Point  |  Coordinates  |  Distance", k, nPoints));
		for (int i=0; i<nPoints; i++) {  //Identify K points closest to origin
			if (distances[i] <= sortedList[k-1]) {
				System.out.println(String.format("  %s    |  (%s, %s)      |   %s", i, pointsList2[i].x, pointsList2[i].y, distances[i]));
			}
		}
	}
	
	private int distance(Point thisPoint) {
		return thisPoint.x*thisPoint.x + thisPoint.y*thisPoint.y;
	}

ArrayList<Double> kNearestPts(Coordinates[] C, int k){
	double[] A = new double[C.length];
	for(int i = 0; i<C.length; i++){
		A[i] = Math.sqrt(C[i].x*C[i].x + C[i].y*C[i].y);
	}
	return selectTopK(A, k);
}

ArrayList<Double> selectTopK(ArrayList<Double> A, int k){
	if(A.size() < 26){
		return selectBruteForce(A, k);
	}
	int m = (A.size()-1)/5 + 1;
	double[] M = new double[m];
	for(int i = 0; i<m; i++){
		M[i] = medianBruteForce(A, 5*i, 5*i + 4);
	}
	ArrayList<Double> mom = selectTopK(M, m/2);
	int r = partition(A, mom.get(mom.size()-1));
	if(k < r+1){
		return selectTopK(new ArrayList<Double>(A.subList(0, r)), k);
	}
	if(k > r+1) {
		return selectTopK(new ArrayList<Double>(A.subList(r+1, A.size()), k-r-1);
	}
	return new ArrayList<Double>(A.subList(0, r+1));
}

ArrayList<Double> selectBruteForce(double[] A, k){
	ArrayList<Double> ret = new ArrayList<Double>();
	while(k > 0){
		int min = Double.MAX_VALUE;
		for(int i = 0; i<A.size(); i++){
			if(A.get(i) < min){
				min = A.get(i);
			}
		}
		ret.add(min);
		A.remove(min);
	}
	return ret;
}

double medianBruteForce(ArrayList<Double> A, int start, int end){
	ArrayList<Double> temp = new ArrayList<Double>();
	for(int i = start; i<= end; i++){
		temp.add(A.get(i));
	}
	for(int i = 1; i<temp.size(); i++){
		for(int j = 0; j<temp.size()-i-1; j++){
			if(temp.get(i) > temp.get(j)){
				double t = temp.get(i);
				temp.set(i, temp.get(j));
				temp.set(j, t);
			}
		}
	}
	return temp.get((0+temp.size())/2);
}
int partition(ArrayList<Double>A, double pivot){
	int r = 0;
	int c = 0;
	while(c < A.size()){
		if(A.get(c) < pivot) {
			double t = A.get(r);
			A.set(r, A.get(c));
			A.set(c, t);
			r ++;
		}
		c++;
	}
	return r;
}

One idea about the solution: 1. Calculate the distances of all points, they will get stored in an array. 2. The question can be attributed to the question to find the smallest k items in an array. To solve this question, we can use several ways, including sorting and find the kth, quicksort like way to partition the array to parts, that all based on the items are not that big enough, they can be loaded into memory.
The following part is sample code to find the Kth number:

public class FindKth {
    public static int findKth(int[] a, int l, int r, int k) {
        int n = partition(l, r);
        int i = n - l + 1;
        if(i > k) {
            return findKth(a, l, n - 1, k);
        } else if(i < k) {
            return findKth(a, n + 1, r, k - i);
        } else
            return n;
    }

    public static int partition(int[] a, int l, int r) {
        int value = a[r];
        int j = l - 1;
        for(int i = l; i < r; i++) {
            if(a[i] < value) {
                j++;
                swap(a, i, j);
            }
        }
        swap(a, j + 1, r);
        
        return j + 1;
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

Use TreeMap to put the points, compared by their distance from origin. Then iterate over the first k.
Complexity: O(nlogn) - n because running over all the elements and logn because the depth of the tree logn.

Here my C++ solution:

typedef struct pos {
	int x;
	int y;
	
	pos(int x_, int y_): x(x_), y(y_) {}
}pos;

typedef struct dist_ind {
	float dist;
	int index;
	dist_ind(float dist_, int index_): dist(dist_), index(index_) {}
}dist_ind;

typedef struct comparison {
	bool operator()(const dist_ind &lhs, const dist_ind &rhs) const {
		return lhs.dist < rhs.dist;
	}
}comparison;

vector<pos> find_k_closest_points(vector<pos> &vec, int k) {
	priority_queue<dist_ind, vector<dist_ind>, comparison> q;
	vector<pos> out;
	
	for(int i = 0; i < vec.size(); i++) {
		float dist = sqrt(pow(vec[i].x, 2) + pow(vec[i].y, 2));
			
		if(q.size() >= k) {
			if(dist < q.top().dist) {
				q.pop();
				q.push(dist_ind(dist, i));
			}
		}
		else {
			q.push(dist_ind(dist, i));
		}
	}
	
	while(!q.empty()) {
		out.push_back(vec[q.top().index]);
		q.pop();
	}
	
	return out;
}

int main() {
	// your code goes here
	
	vector<pos> vec = {{2,2}, {6,6}, {4,4}, {5,5}, {3,3}, {9,9}, {7,7}, {8,8}, {10,10}};  
	vec = find_k_closest_points(vec, 2);
	
	for_each(vec.begin(), vec.end(), [](pos &p) { cout << p.x << ", " << p.y << endl;});
     
	return 0;
}

Did a solution in golang see comment for explanation:

package main

import (
	"fmt"
	"math"
)

func main() {
	arr := []Point{Point{X: 3, Y: 40}, Point{X: 19, Y: 4}, Point{X: 7, Y: 4}, Point{X: 1, Y: 4}, Point{X: 17, Y: 4}, Point{X: 11, Y: 4}}
	fmt.Println(Closest(arr, 2))
}

type Point struct {
	X int
	Y int
}

func (point Point) distance() float64 {
	a := math.Pow(float64(point.X), 2)
	b := math.Pow(float64(point.Y), 2)
	return math.Sqrt(a + b)
}

func Closest(points []Point, k int) []Point {
	position := selection(points, k)

	//return slice of k closest points
	return points[0:position]
}

//Quick Selection algorithm
//Basically what amounts to a partial insertion sort
//Customized for Point struct
//Return position kth Point
func selection(arr []Point, k int) int {
	to := len(arr) - 1
	for from := 0; from < to; {
		read := from
		write := to
		midV := arr[(read+write)/2].distance()

		for read < write {
			if arr[read].distance() >= midV {
				swap(arr, read, write)
				write = write - 1
			} else {
				read = read + 1
			}
		}

		if arr[read].distance() > midV {
			read = read - 1
		}

		if k <= read {
			to = read
		} else {
			from = read + 1
		}
	}
	return k
}

func swap(arr []Point, i int, j int) {
	temp := arr[i]
	arr[i] = arr[j]
	arr[j] = temp
}

Given k = 2 and initial points array:

var k = 2, 
	arr = [{x:1,y:2}, {x:2, y:0}, {x:4, y:0}, {x:1, y:2}], 
	length = arr.length, 
	result = [];

for(i = 0; i< length; i+=1){
  arr[i].radius = Math.sqrt(arr[i].x*arr[i].x + arr[i].y+arr[i].y);
}

arr.sort(function(a, b) {
  return a.radius - b.radius;
});

for(i = 0; i< k; i+=1){
  result.push(arr[i]);
}