CareerCup

/* The complexity of the following solution is O(nlogn) for n points in the plane. The idea is to sort the distances between the center and all the points in the plane and return the m points which are the closest*/

public class Point implements Comparable{
double x;
double y;
Double distFromCenter = null;

public Double getDistFromCenter() {
return distFromCenter;
}
public void setDistFromCenter(double distFromCenter) {
this.distFromCenter = distFromCenter;
}
public Point(double x, double y) {
super();
this.x = x;
this.y = y;
}
public double getX() {
return x;
}
public void setX(double x) {
this.x = x;
}
public double getY() {
return y;
}
public void setY(double y) {
this.y = y;
}

public int compareTo(Object y){
Double y_distFromCenter = ((Point)y).getDistFromCenter();
if (distFromCenter != null && y_distFromCenter != null){
if (distFromCenter == y_distFromCenter){
return 0;
}else if (distFromCenter > y_distFromCenter){
return 1;
}else{
return -1;
}
}
else
return 0;
}
}

import java.util.*;


public class PointsOnAPlaneImpl implements PointsOnAPlane{

ArrayList<Point> points = new ArrayList<Point>();

@Override
public void addPoint(Point point) {
points.add(point);

}

@Override
public ArrayList<Point> findNearest(Point center, int m) {
// TODO Auto-generated method stub
PriorityQueue<Point> q = new PriorityQueue<Point>();
for (Point p : points){
double dist = Math.pow((center.getX() - p.getX()),2) + Math.pow((center.getY() - p.getY()),2) ;
p.setDistFromCenter(dist);
q.add(p);
}
ArrayList<Point> nearestPoints = new ArrayList<Point>();
for (int i = 0; i < m; i++){
nearestPoints.add(q.poll());
}
return nearestPoints;
}

public static void main (String[] args){
PointsOnAPlaneImpl p = new PointsOnAPlaneImpl();
// (0, 1) (0, 2) (0, 3) (0, 4) (0, 5)
p.addPoint(new Point(0,1));
p.addPoint(new Point(0,2));
p.addPoint(new Point(0,3));
p.addPoint(new Point(0,4));
p.addPoint(new Point(0,5));

ArrayList<Point> nearestPoints = p.findNearest(new Point(0, 0), 3) ;

for (Point point: nearestPoints){
System.out.println(point.getX() + "," + point.getY());
}
}


}

Abhinav, how was interview process in Linkedin? Can you share your experience?

for each point calculate distance to the center in O(n)
create heap in O(n)
pop m times from the heap in O(m)

Solution is:

priority queue size 'm' (m = m nearest)
For each point in points:
	if priorityQueue is not full:
		add to queue;
	else:
		if point < priorityQueue.top() {
			pop the top element;
			push the new element

to check distance use pythagoras theorem

Sqrt (point.x^2 + point.y ^2)

In scala

def neighbors(center:(Int, Int), points:Seq[(Int, Int)], m:Int) = {
	  points.diff(Seq(center)).map(t=>((t._1-center._1)*(t._1-center._1)+(t._2-center._2)*(t._2-center._2), t)).sorted.take(m).map(t=>t._2)
	}

In scala

def neighbors(center:(Int, Int), points:Seq[(Int, Int)], m:Int) = {
	  points.diff(Seq(center)).map(t=>((t._1-center._1)*(t._1-center._1)+(t._2-center._2)*(t._2-center._2), t)).sorted.take(m).map(t=>t._2)
	}

I feel that the problem is already answered but I have one question regarding calculating the distance. Since we are eventually comparing the relative distance, will it be okay and efficient to use distance which is: |x2 - x1| + |y2 - y1|.
This may be a pre-mature optimization, but what do you think?

#include <iostream>
#include <vector>
#include <math.h>
#include <queue>

using namespace std;

struct Point {
    int x,y;
    Point(int a,int b) : x(a), y(b) {}
};

struct PointWithDist {
    int id;
    double dist;
    PointWithDist(int i, double d) : id(i),  dist(d) {}
};

class Compare {
    public :
    bool operator() (const PointWithDist& a, const PointWithDist& b) const {
        return a.dist < b.dist;
    }
};

double calcDist(Point& a, Point& b) {
    double x = abs(a.x-b.x);
    double y = abs(a.y-b.y);
    return sqrt(pow(x,2)+pow(y,2));
}

vector<Point> findNearest(Point c, int m, vector<Point>& points) {
    priority_queue<PointWithDist, vector<PointWithDist>, Compare> pq;
    for (int i = 0; i < points.size(); ++i) {
        double d = calcDist(c,points[i]);
        if (pq.size() < m) {
            pq.push(PointWithDist(i,d));
        } else if (pq.size() > 0 && d < pq.top().dist) {
            pq.pop();
            pq.push(PointWithDist(i, d));
        }
        cout << "pq.top : " << pq.top().dist << "\n";
    }

    vector<Point> result;
    while(!pq.empty()) {
        result.push_back(points[pq.top().id]);
        pq.pop();
    }
    return result;
}

int main() {
    vector<Point> points;
    points.push_back(Point(0,1));
    points.push_back(Point(0,2));
    points.push_back(Point(0,4));
    points.push_back(Point(0,2));
    points.push_back(Point(2,4));
    vector<Point> result = findNearest(Point(0,0),3, points);
    for (int i =0; i < result.size(); ++i) {
        cout << "x : " << result[i].x << "\ty : " << result[i].y << "\n";
    }
}

public static Collection<Point> findNearest(List<Point> list, Point center, int m) {

		list.stream().sorted((a, b) -> Double.compare(distanceInPlane(a, center), distanceInPlane(b, center)));

		return list.subList(0, m);

	}

	public static double distanceInPlane(Point a, Point b) {
		return Math.sqrt(Math.pow(Math.abs(a.x - b.x), 0.5) + Math.pow(Math.abs(a.y - b.y), 0.5));
	}

class Point {
	int x;
	int y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}