chessplayer
BAN USERBut Like to know, when there are utility methods to sort still Interview expect to write a fresh sort?
Running code sample below with Two possible ways to solve this:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.Random;
import java.util.TreeMap;
public class PuzzleRunner {
public static void main(String[] args) {
try {
Plane2D plane2d = new PuzzleRunner().new Plane2D(10,5);
plane2d.fillRandomPoints(10);
plane2d.showGenetatedPoints();
System.out.println("Result by n log(n) performance" + plane2d.getClosedPoint());
System.out.println("guaranteed log(n) time cost" +plane2d.getClosedPoint2());
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
protected class Plane2D {
private int length;
private int breath;
private ArrayList<Point> points;
Plane2D(int length, int breath) throws Exception{
if(length <= 0 || breath <= 0){
throw new Exception("Size is less then zeros not allowed in this version");
}
this.length = length;
this.breath = breath;
}
public void fillRandomPoints(int numberOfPoints){
points = new ArrayList<Point>(numberOfPoints);
Random randomX = new Random();
Random randomY = new Random();
for (int i = 0; i < numberOfPoints; i++) {
points.add(new Point(randomX.nextInt(length), randomY.nextInt(breath)));
}
}
public Point getClosedPoint(){
/**
* The sorting algorithm is a modified merge sort
* This algorithm offers guaranteed n log(n) performance
*/
Collections.sort(points);
return points.get(0);
}
public Point getClosedPoint2(){
//This implementation provides guaranteed log(n) time cost for the containsKey
TreeMap<Double, Point> treeMap = new TreeMap<Double, Point>();
for (Point point : points) {
treeMap.put(point.getDistanceOfPointsFromOrigin(), point);
}
return treeMap.get(treeMap.firstKey());
}
public void showGenetatedPoints(){
for (Iterator<Point> iterator = points.iterator(); iterator.hasNext();) {
Point point = (Point) iterator.next();
System.out.println(point);
}
}
}
protected class Point implements Comparable<Point> {
private double x;
private double y;
private double distanceOfPointsFromOrigin;
Point(double x, double y){
this.x = x;
this.y = y;
this.distanceOfPointsFromOrigin = Math.sqrt(getX()*getX() + getY()*getY());
}
public double getX() {
return x;
}
public double getY() {
return y;
}
@Override
public int compareTo(Point o) {
if(this.distanceOfPointsFromOrigin < o.getDistanceOfPointsFromOrigin()){
return -1;
}else if (this.distanceOfPointsFromOrigin > o.getDistanceOfPointsFromOrigin()){
return 1;
}else{
return 0;
}
}
@Override
public String toString() {
return "Point [x=" + x + ", y=" + y + "]";
}
public double getDistanceOfPointsFromOrigin() {
return distanceOfPointsFromOrigin;
}
}
}
Repdubinalinda4, Animator at Apache Design
Hello, I am a school librarian from Lewistown USA. I work in public or private schools at elementary, middle and ...
- chessplayer October 18, 2013