Main.java

/*
 * Exercise from http://programmingpraxis.com/2012/11/27/amazon-interview-question/
 * Given a million points (x, y), give an O(n) solution to find the 100 points closest to (0, 0).
 * Well, you have to read "a million" as "n" and "100" as "100".
 * Uses a heap of size 100. The complexity-theoretic trick is that 100 is a constant here.
 */

import java.io.File;
import java.io.FileNotFoundException;
import java.util.PriorityQueue;
import java.util.Scanner;


public class Main {
	
	static int MAX_PRIORITY_QUEUE_SIZE = 100;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		try {
			PriorityQueue<Point> pq = new PriorityQueue<Point>(MAX_PRIORITY_QUEUE_SIZE, new ReversePointComparator());
			if(args.length == 0) {
				System.out.println("Give me a filename");
				System.exit(0);
			}
			Scanner sc = new Scanner(new File(args[0]));
			int n = sc.nextInt();
			Point num;
			for(int i=0; i<MAX_PRIORITY_QUEUE_SIZE && i<n; i++) {
				num = new Point(sc.nextDouble(), sc.nextDouble());
				pq.add(num);
			}
			for(int i=MAX_PRIORITY_QUEUE_SIZE; i<n; i++)
			{
				num = new Point(sc.nextDouble(), sc.nextDouble());
				if(num.getDist() < pq.peek().getDist())
				{
					pq.poll();
					pq.add(num);
				}
			}
			Point [] pts = new Point[pq.size()];
			pts = pq.toArray(pts);
			for(int i=0; i<pts.length; i++)
				System.out.print(pts[i] + " ");
			System.out.println();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}

}

Point.java

public class Point {
	
	double x,y;
	double dist;
	public Point(double d, double e) {
		this.x = d;
		this.y = e;
		dist = Math.sqrt(d*d + e*e);
	}
	
	public double getDist() {
		return dist;
	}
	
	@Override
	public String toString() {
		return "(" + x +" ," + y +")";
	}

}

ReversePointComparator.java

import java.util.Comparator;


public class ReversePointComparator implements Comparator<Point> {

	@Override
	public int compare(Point p1, Point p2) {
		return (int) (p2.getDist() - p1.getDist());
	}

}