JonG
BAN USERUpdated solution.
This one is designed for practical use. In a typical scenario, I would expect to be given a very large number of points (i.e. 10,000,000) to search through & only a small number of k-points (i.e. 15 or less) that need to be returned.
Storing 10-million pointers and their distance values, or 'cheating' by having a point class that stores it's distance from (0,0) (what?!) would be extremely inefficient. Instead, we just store the k-closest points so far, and their distances.
As far as calculations, we save by using distance-squared and storing those distances.
For fun, I ran a test on my old laptop with 10-million random points and 15-closest, and the results returned in 125ms.
// test the code
public static void main(String[] args) {
Vect2[] points = randPts(25, 10f);
Vect2[] points2 = vectDistSorter(5, new Vect2(0, 0), points);
System.out.println("Starting Points"); //print results
for (Vect2 point : points) {
System.out.println("point: " + point);}
System.out.println("===============");
System.out.println("Results");
for (Vect2 point : points2) {
System.out.println("point: " + point);}
}
//generate test points
public static Vect2[] randPts(int total, float scalar) {
Vect2[] points = new Vect2[total];
for (int i = 0; i < total; i++) {
points[i] = new Vect2((float) Math.random() * scalar,
(float) Math.random() * scalar);
}
return points;
}
/**
* Returns the closest K-points to the targetPt, from points array. Uses
* O(k) memory and worst case is O(points*k). This solution is ideal for a
* large number of points (i.e. 10000000) and a small number of k-closest
* (i.e. 10).
*/
public static Vect2[] vectDistSorter(int kClosest, Vect2 targetPt,Vect2[] points) {
VectSortData vData = new VectSortData();
vData.vect = new Vect2[kClosest];
vData.dist2 = new float[kClosest];
vData.totalPts = kClosest;
vData.targetPt = targetPt;
if (kClosest >= points.length) {
return points;
}// done early, that was easy!
for (int i = 0; i < kClosest; i++) {// add first k points
vData.vect[i] = points[i];
vData.dist2[i] = vData.dist2FromPt(points[i]);
}
vData.selectNextMax();
float curDist;
for (int i = kClosest, len = points.length; i < len; i++) {// if closer,
// replace
// farthest
// point
curDist = vData.dist2FromPt(points[i]);
if (curDist < vData.curMaxDist) {
vData.vect[vData.curMaxIndex] = points[i];// replace max pt
vData.dist2[vData.curMaxIndex] = curDist;// replace distance
vData.selectNextMax();// selext new farthest point
}
}
return vData.vect;
}
// helper class that stores temporary closest-point data & does a couple opperations
static class VectSortData {
Vect2 vect[];// stores points
float dist2[];// stores distance-squared
Vect2 targetPt;// oritionating point
int totalPts;// number of closest points
float curMaxDist = 0;// distance of farthest point in our current list
int curMaxIndex = 0;// cursor of current max. Saves searches
float xDist;// less garbage collection
float yDist;// less garbage collection
// we only need the squared-distance.
float dist2FromPt(Vect2 vect) {
xDist = (vect.x - targetPt.x);
yDist = (vect.y - targetPt.y);
return xDist * xDist + yDist * yDist;
}
//searches for the next max-distance point & stores the distance and index
void selectNextMax() {
curMaxDist = 0;
for (int i = 0; i < totalPts; i++) {
if (dist2[i] > curMaxDist) {
curMaxDist = dist2[i];
curMaxIndex = i;
}
}
}
}
// We need a points class to contain the points.
public static class Vect2 {
public float x;
public float y;
public Vect2(float x, float y) {
this.x = x;
this.y = y;
}
@Override public String toString() {return "[" + x + "," + y + "]";}
}
public static void main(String[] args) {
Map<Integer, String> lookups = new HashMap<Integer, String>();
lookups.put(3, "Fizz");
lookups.put(5, "Buzz");
lookups.put(7, "Wolf");
fizzbuzz(-10, 120, lookups);
}
public static List<String> fizzbuzz(int start, int end, Map<Integer, String> lookups) {
List<String> list = new ArrayList<String>(end-start+1);
Set<Entry<Integer, String>> entrySet = lookups.entrySet();
String out = "";
for (int i = start; i < end+1; i++) {
out = i+": ";
for (Entry<Integer, String> entry: entrySet) {
if (isMultOf(i, entry.getKey())){
out+= entry.getValue();
}
}
list.add(i-start, out);
System.out.println(out);//TODO for testing purposes.
}
return list;
}
public static boolean isMultOf(int val, int mult) {
return val%mult == 0;
}
Tested and works.
/*Write a program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz".
For numbers which are multiples of both three and five print "FizzBuzz".
Additionally, instead of printing "Fizz" or "Buzz", create a lookup such that 3 --> "Fizz", 5 --> "Buzz", 7 --> "Woof" and so on. The signature of the method would be:
List<String> fizzbuzz(int start, int end, Map<Integer, String> lookups) { ..}
The expected output is of the format : 15:FizzBuzz, 21:FizzWoof, 105: FizzBuzzWoof, etc*/
public static void fizzBuzzStuffs() {
boolean is3 = false, is5 = false, is7 = false;
String out = "";
for (int i = 0; i < 100; i++) {
is3 = isMultOf(i, 3);
is5 = isMultOf(i, 5);
is7 = isMultOf(i, 7);
out = "";
if (!is3 && !is5 && !is7) {
System.out.println(i);
} else {
out = "";
if (is3){out += "Fizz"; }
if (is5){out += "Buzz"; }
if (is7){out += "Wolf"; }
System.out.println(out);
}
}
}
public static boolean isMultOf(int val, int mult) {
return val%mult == 0;
}
Not elegant, but it works. (Java) Could probably make the code more elegant with more time.
//test the code
public static void main(String[] args) {
Vect2[] points = {new Vect2(1, 1),new Vect2(2, 2),new Vect2(3, 2),new Vect2(0, 1),new Vect2(1, 0)};
Vect2[] points2 = getKclosest(points, 3);
for (int i = 0; i < points2.length; i++) {
System.out.println("point: "+points2[i]);
}
}
public static Vect2[] getKclosest(Vect2[] points, int k) {
//ArrayList<VectData> list = new ArrayList<VectData>(points.length);
VectData[] list = new VectData[points.length];
for (int i = 0, len = points.length; i < len; i++) {
list[i]= new VectData(points[i]);}
Arrays.sort(list);
Vect2[] points2 = new Vect2[k];
for (int i = 0; i < k; i++) {
points2[i] = list[i].getVect();
}
return points2;
}
public static class VectData implements Comparable<VectData>{
private Vect2 vect;
private float dist2;//distance squared
public float getDist2() {
return dist2;}
public Vect2 getVect(){
return vect;}
public VectData (Vect2 vect) {
this.vect = vect;
dist2 = dist2FromZero(vect);
}
public float dist2FromZero(Vect2 vect) {//we only need the squared-distance. Less calc.
return vect.x*vect.x+vect.y*vect.y;
}
@Override
public int compareTo(VectData o) {
return (o.getDist2() < this.getDist2())?1:-1;
}
}
public static class Vect2 {
public float x;
public float y;
public Vect2(float x,float y){
this.x=x; this.y=y;}
@Override public String toString() {
return "["+x+","+y+"]";
}
}
@Miguel True & thank you for the review.
I suppose it depends on the memory/processor constraints and expected input. Mine involves the least number of steps, but uses more memory. Yours has about 2x the steps, and destroys the original array in the process. The top-voted comment is quite clever, using a 'negative' flag, but in the process performs about 3x the operations without destroying the original array.
I only recently began these types of interviews, and noticed they're much more picky about memory usage than they are the number of steps in the process.
Could you give an example? I could probably 'invent' something, but I'm not familiar with the default/standardway (and i'm always interested in learning)
- JonG October 19, 2013