Instantly share code, notes, and snippets.

# varzan/Main.java Created Nov 27, 2012

 /* * 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 pq = new PriorityQueue(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
 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 +")"; } }
 import java.util.Comparator; public class ReversePointComparator implements Comparator { @Override public int compare(Point p1, Point p2) { return (int) (p2.getDist() - p1.getDist()); } }