Created
November 27, 2012 20:01
-
-
Save varzan/4156657 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* 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(); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 +")"; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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