public
Created

  • Download Gist
Main.java
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
/*
* 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
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
 
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
Java
1 2 3 4 5 6 7 8 9 10 11
import java.util.Comparator;
 
 
public class ReversePointComparator implements Comparator<Point> {
 
@Override
public int compare(Point p1, Point p2) {
return (int) (p2.getDist() - p1.getDist());
}
 
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.