Skip to content

@varzan /Main.java
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
/*
* 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();
}
}
}
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<Point> {
@Override
public int compare(Point p1, Point p2) {
return (int) (p2.getDist() - p1.getDist());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.