CareerCup

Use a max heap.
Store only 'k' elements(points w.r.t distances from (0,0)) in the max heap at a time.
Once you get a new point insert it into the max heap and remove the largest element from the heap.
After the completion of traversal, the max heap will contain 'k' nearest neighbours to the point (0,0).

First step is to calculate the distance for each point = sqrt(x * x + y * y).
Next step is to fint the K points with the smallest distance.

One way is just to sort the points by their distance and list K first items in the resulting list - this would obviously have a complexity of O(N log N).

Another way would be to insert the points into a binary min heap of length K while calculating the distances - this would have a complexity of O(N log K) which might be beneficial (in terms of time and space) if K is much smaller than N.

Using Java 8 solution:

1. keep a field in Point class called distanceFromOrigin, which will be calculated when the point is created. The formula is based on Euclidian distance formula for distance between points in a 2d Map.

2. Create a Comparator class that compares points based on their distance from origin.

3. Create a list that will store the points of the sample.

4. Use Java 8 Stream api on List to sort by PointDistanceToOrigin Comparator and limit max results as K and print the results to System.out

public class Solution {

	public static void main(String args[]) {

		Point p1 = new Point(1, 3, findDistanceOfPoints(1, 3, 0, 0));
		Point p2 = new Point(3, 4, findDistanceOfPoints(3, 4, 0, 0));
		Point p3 = new Point(-1, 5, findDistanceOfPoints(-1, 5, 0, 0));
		Point p4 = new Point(-2, 2, findDistanceOfPoints(-2, 2, 0, 0));
		Point p5 = new Point(2, 3, findDistanceOfPoints(2, 3, 0, 0));

		List<Point> ptList = new ArrayList<Point>();

		ptList.add(p1);
		ptList.add(p2);
		ptList.add(p3);
		ptList.add(p4);
		ptList.add(p5);

		int k = 3;

		printClosestPointsToOrigin(ptList, k);

	}

	public static void printClosestPointsToOrigin(List<Point> ptList, int k) {

		// sort by distance from origin and print
		ptList.stream().sorted(PointDistanceFromOriginComparator.INSTANCE)
				.limit(k).forEach(System.out::println);
	}

	public static int findDistanceOfPoints(int x1, int x2, int y1, int y2) {
		Double dist = Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
		return dist.intValue();
	}

}

class Point {
	Integer x, y;
	Integer distanceFromOrigin;

	public Point(Integer x, Integer y, Integer distO) {
		this.x = x;
		this.y = y;
		this.distanceFromOrigin = distO;
	}

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

class PointDistanceFromOriginComparator implements Comparator<Point> {

	public static final PointDistanceFromOriginComparator INSTANCE = new PointDistanceFromOriginComparator();

	public int compare(Point p1, Point p2) {
		if (p1.distanceFromOrigin < p2.distanceFromOrigin) {
			return -1;
		} else if (p1.distanceFromOrigin > p2.distanceFromOrigin) {
			return 1;
		}
		return 0;
	}
}

Use knn-algorithm to calculate Euclidean distance!!

One advantage is that we know that one of the points is the origin (0,0) so that can simplify the maths from Math.Sqrt(Math.Pow(p2.X - p1.X, 2) + Math.Pow(p2.Y - p1.Y, 2)) to just sum of the absolute values of the point Math.Abs(p1.X) + Math.Abs(p1.Y) and sort using this criteria.
This is my solution in C#

public class Point
{
public Point(int x, int y)
{
this.X = x;
this.Y = y;
}
public int X;
public int Y;
}

// Like we are searching the nearest points to the point (0,0) we don't need all the maths
// Math.Sqrt(Math.Pow(y.X - x.X, 2) + Math.Pow(y.Y - x.Y, 2));
private class PointComparer : IComparer<Point>
{
public int Compare(Point x, Point y)
{
// just a relative distance from the origin {0, 0} to the point;
int distance1 = Math.Abs(x.X) + Math.Abs(x.Y);
int distance2 = Math.Abs(y.X) + Math.Abs(y.Y);

return distance1.CompareTo(distance2);
}
}

Point[] GetNearestPoints(Point[] points, int k)
{
if (k <= 0 || points == null || points.Length == 0)
return null; //new Point[0];

Array.Sort(points, new PointComparer());

Point[] result = new Point[k];
for (int i = 0; i < k; i++)
result[i] = points[i];

return result;
}

One advantage is that we know that one of the points is the origin (0,0) so that can simplify the maths from Math.Sqrt(Math.Pow(p2.X - p1.X, 2) + Math.Pow(p2.Y - p1.Y, 2)) to just sum of the absolute values of the point Math.Abs(p1.X) + Math.Abs(p1.Y) and sort using this criteria.

This is my solution in C#

{
public class Point
{
public Point(int x, int y)
{
this.X = x;
this.Y = y;
}
public int X;
public int Y;
}

// Like we are searching the nearest points to the point (0,0) we don't need all the maths
// Math.Sqrt(Math.Pow(y.X - x.X, 2) + Math.Pow(y.Y - x.Y, 2));
private class PointComparer : IComparer<Point>
{
public int Compare(Point x, Point y)
{
// just a relative distance from the origin {0, 0} to the point;
int distance1 = Math.Abs(x.X) + Math.Abs(x.Y);
int distance2 = Math.Abs(y.X) + Math.Abs(y.Y);

return distance1.CompareTo(distance2);
}
}

Point[] GetNearestPoints(Point[] points, int k)
{
if (k <= 0 || points == null || points.Length == 0)
return null; //new Point[0];

Array.Sort(points, new PointComparer());

Point[] result = new Point[k];
for (int i = 0; i < k; i++)
result[i] = points[i];

return result;
}
}

use strict;

# the node information were stored as "x	y	id" in the node_list.txt, such as "4	3	id1".
open(FH,'node_list.txt');
my @nodes = <FH>;
close FH;
my %distance;
foreach (@nodes) {
	chomp;
	my @temp_node = split("\t",$_);
	my $x= @temp_node[0];  #x-axis 
	my $y= @temp_node[1];  #y-axis
	my $node_id = @temp_node[2]; #nodes_id;
	$distance{$node_id}=$x*$x+$y*$y; #same as sqrt result;
}
print %distance."\n";
my @sort_dist = sort {$distance{$a} <=> $distance{$b}} keys %distance;
my $i=0;
#print their related distance
foreach (@sort_dist[0..19]) {
	$i +=1; 
	printf "#".$i." node: ".$_.", distance: %.2f\n", sqrt($distance{$_});
}
print "\n";

sort by distance from the (0,0);

int compare(Point a, Point b) {
Integer d1 = a.x * a.x + a.y * a.y;
Integer d2 = b.x * b.x + b.y * b.y;
return d1 - d2;
}

return the first k element of the sorted array;