## Linkedin Interview Question for Software Engineer / Developers

• 0

Country: United States

Comment hidden because of low score. Click to expand.
2
of 4 vote

/* 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

}

@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);
}
ArrayList<Point> nearestPoints = new ArrayList<Point>();
for (int i = 0; i < m; i++){
}
return nearestPoints;
}

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

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

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

}

Comment hidden because of low score. Click to expand.
2

Nice solution. This is indeed O(n log(n)). However, I think that if you use a TreeSet instead of a PriorityQueue, I think you can bring it down to O(n log(m)). If m << n, this can make a huge difference! :)

Comment hidden because of low score. Click to expand.
0

I think

``findNearest``

should be complexity O(1) but adding O(n logn), so need to ask interviewer what operation is most often and sort points on adding or on searching.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Sorting is not neccessary. Compute the distances, find the mth-nearest distance (can be done in linear, search for selection algorithm), then iterate all the points once again and return those with the smaller distance from the center than the m-th nearest. Only ties with m-th nearest must be handled specially but that is an easy one.

Total complexity O(n)

Comment hidden because of low score. Click to expand.
0

Killedsteel, TreeSet won't work, as it won't allow duplicates. A priorityQueue, in particular a max heap works for the problem. We just need to keep the heap size to be at most m, by removing heap root during the scan when a number smaller than root is found. This can still make O(n log(m)) complexity. See my java code snippet below.

``````PriorityQueue<Point> heap = new PriorityQueue<Point>(m, new Comparator<Point>() { //max heap
@Override
public int compare(Point a, Point b) {
return Integer.compare(b.distance2(center), a.distance2(center));
}
});

for(int i=0; i<points.size(); i++) { //O(n)
Point p = points.get(i);
if (p==center) continue; //use reference equals as there may be other points with the same coordinates as the center.
else {
if (p.distance2(center)<heap.peek().distance2(center)) { //O(1)
heap.remove(); //O(log(m));
}
}
}``````

Comment hidden because of low score. Click to expand.
0

Can be even simpler

``````for(int i=0; i<points.size(); i++) { //O(n)
Point p = points.get(i);
if (p==center) continue;
if (heap.size()>m) heap.remove();
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

Comment hidden because of low score. Click to expand.
0

Insertion and removal in the heap is log(n), hence you have to at least spend o(n*log(n)) time.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution is:

``````priority queue size 'm' (m = m nearest)
For each point in points:
if priorityQueue is not full:
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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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";
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.