## Facebook Interview Question for Web Developers

• 2

Country: United States
Interview Type: Phone Interview

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

Solution 1: min-priority queue where the key for each point is the distance to (0,0). Heapify the input array and pop first K. Complexity: O(n+k*log(n))
Solution 2: use a selection algorithm like quick select to get Kth closest element. Complexity: O(n) average, O(n*n) worst case. You'll get a partially sorted array where Kth element is on it's place and all elements to the left are closer to (0,0) or same distance. Note that the complexity of this method does not even depend on K.

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

As in the first answer compute √(x - a)² + (y - b)² distance
Each time you get an answer put it into a priority heap.
When the number of items in the queue gets to n compare the new value to the top of the heap.
If the new value is better than the worst in the queue toss it out and replace it with the new one.
This way you don’t have to keep all values around.
You could consider loading the first n in to the priority queue first and only then heapifying it. That will save a little time.
Roots don’t come cheap so just consider the distance squared.
Squares don’t come cheap either so you could compute the abs of the Xs and Ys and dismissing points who's X or Y value is larger than the worst distance in the heap.

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

This is how I'd do it,
1 get the points, populate in an ArrayList
2 call Collections.sort on the list with user defined Comparator
3 print the first n points
Note: If we don't use an ArrayList store the points in an array, manually sort the array using the Euclidean distance
simplifications done:
1 Distance from origin sqrt(x^2+y^2)
2 removal of sqrt from the equation cause squares, square roots and n considered here are always proportional under the given problem circumstances

``````public class NClosePoints
{
static List<Point> list;

public static void main(String[] args)
{
list = new ArrayList<>();
Scanner in = new Scanner(System.in);
System.out.print("Enter no of points : ");
int size = in.nextInt();int i;
for (i = 0; i < size; i++) {
Point tmp = new Point(in.nextInt(), in.nextInt());
}
System.out.print("Enter N of N closest points needed : ");
int n = in.nextInt();
Collections.sort(list, new Comparator<Point>(){
@Override
public int compare(Point p1,Point p2){
return (int) ((Math.pow(p1.x, 2)+Math.pow(p1.y, 2))-(Math.pow(p2.x, 2)+Math.pow(p2.y, 2)));
}
});
i=0;
for (Point tmp : list) {
if(i<n)
System.out.println("Point "+(i+1)+" : "+tmp);
else
break;
i++;
}
}

static class Point
{
int x, y;

Point(int i, int j)
{
x = i;
y = j;
}

@Override
public String toString(){
return "( "+x+" , "+y+" )";
}
}
}``````

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

An important observation is that we can use the square of euclidean distance and it will keep the order. This is very helpful to avoid lose precision.

So the logic is:

1. Calculate the distance for every node and keep it in an array with the index of that node.
2. Sort this array.
3. Return the first N elements.

Time complexity O(M)
Memory complexity O(M)

Code:

``````vector<pair<int, int> > nClosePoints(vector<pair<int,int> > graph, int n){
vector<pair<long long, int> > distance;
for(int i=0;i<graph.size();i++){
long long dist=graph[i].first+graph[i].second;
distance.pb({dist,i});
}
sort(distance.begin(), distance.end());
vector<pair<int,int> > ans;
for(int i=0;i<n;i++)ans.pb(graph[distance[i].second]);
return ans;
}``````

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

Optimized in heap size.
public class ClosestPoints {

public static void main(String[] args) {
int max = 9;

FixedSizedPriorityQueue<Point> queue = new FixedSizedPriorityQueue<Point>(max,
(x, y) -> {
return x.getDistance().compareTo(y.getDistance());
}
);

List<Point> points = Arrays.asList(new Point(1,9), new Point(6,3),new Point(1,5),
new Point(8,3),new Point(5,6),new Point(5,5),new Point(7,6),
new Point(2,8), new Point(8,1));

System.out.println("The closest "+ max + " points are as follows");
while(queue.peek() != null) {
System.out.println(queue.poll().toString());
}
}

}
class Point{
final int x,y;
final double distance;
Point(int x, int y){
this.x = x;
this.y = y;
this.distance = Math.sqrt(x*x+y*y);
}
public Double getDistance() {
return -distance;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return "("+ x + ","+y+")";
}
}

public class FixedSizedPriorityQueue<T> {

private final int maxSize;
private final PriorityQueue<T> pqueue;
FixedSizedPriorityQueue(int size, Comparator<T> comparator){
this.maxSize = size;
this.pqueue = new PriorityQueue<T>(maxSize, comparator);

}

if(pqueue.size() < maxSize) {
} else {
if(pqueue.comparator().compare(pqueue.peek(),item) < 1) {
pqueue.poll();
}
}
}
T peek() {
return pqueue.peek();
}

T poll() {
return pqueue.poll();
}
}

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

``````import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

public class Main {

public static void main(String[] args) {

// input setup
List<int[]> list = new ArrayList<int[]>();

// try TreeMap as it supports sort in ascending order
// distance and point
TreeMap<Integer, int[]> inputs = new TreeMap<Integer, int[]>();

// for distance, we only need relative length, so root is not required.
for (int i = 0; i < list.size(); i++) {
inputs.put(list.get(i)*list.get(i) + list.get(i)*list.get(i), list.get(i));
}

// for a given 'n', return relevant elements from the list
int n = 3;
ArrayList<int[]> out = new ArrayList<int[]>();
for (int i = 0; i < n; i++) {
}

// check
for (int i = 0; i < out.size(); i++) {
System.out.println(out.get(i) + ", " + out.get(i));
}
}
}``````

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

Using Priority Queue this can be implemented in Python. The other optimized solution is to use max heap where the max element is stored in the heap.

import math
from Queue import PriorityQueue

class Soln(object):
def mindistanc(self, list, n):
if len(list) == 0:
return 0

for points in list:
ed = sqrt(a*a + b*b)
q.put(ed, (a,b))
k = 0
while q.empty() and k < n:
value, points = q.get(value, points)
rlist.append(points)
k += 1

return rlist

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

This may be not the best solution but is very understandable O(n+n*log(n))

``````# We remove sqrt because it wont change the output result
def euclideanDist(x, y): # the distance to 0,0
return pow(x,2)+pow(y,2)

def sort(array):
less = []
equal = []
greater = []

if len(array) > 1:
pivot = array
for x in array:
if x < pivot:
less.append(x)
if x == pivot:
equal.append(x)
if x > pivot:
greater.append(x)
return sort(less)+equal+sort(greater)
else:
return array

# the kth closest points to (0,0)
k = 2
points = [(1,5),(3,2),(66,12),(9,15),(22,14),(13,25),(20,56),(5,9)]
distances = [euclideanDist(p, p) for p in points] # we populate an array of distances

print (sort(distances)[0:k]) # we sort the distances and show the first k``````

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

``````from math import sqrt

def get_closest(points,n):
points = sorted(points, key=lambda a:sqrt(pow(a,2)+pow(a,2)))
return points[:n]``````

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

``````import java.util.*;

public class NodeDistances {
static final class Node implements Comparable<Node> {
public int index;
public long distance;
@Override
public int compareTo(Node m)
{
if (m.distance > this.distance)
return 1;
if (m.distance < this.distance)
return -1;
return 0;
}
public Node(int index, long distance)
{
this.index = index;
this.distance = distance;
}
}

public static List<long[]> closestToOrigin(long[][] points, int k) {
List<long[]> result = new ArrayList<>();
if (k <= 0) {
return result;
}

Queue<Node> distances = new PriorityQueue<>();
for (int i=0; i<points.length; i++) {
long distance = points[i]*points[i] + points[i]*points[i];
if (distances.size() == k && distances.peek().distance > distance) {
distances.poll();
} else if (distances.size() < k) {
}
}
while (!distances.isEmpty()) {
Node n = distances.poll();
}
return result;
}

public static void main(String args[]){
long[][] points = {{1,1}, {1,2}, {1,5}, {1,-3}, {-1,2}};
List<long[]> result = closestToOrigin(points, 3);
result.forEach(i -> {
System.out.println(Arrays.toString(i));
});
}
}``````

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

``````void print_k_closest_to_origin(const std::vector<Point>& points, int k) {
std::vector<Point> heap(points);
auto cmp = [](const Point& a, const Point& b) { return a.x * a.x + a.y * a.y > b.x * b.x + b.y * b.y;  };
std::make_heap(heap.begin(), heap.end(), cmp);
for (int i = 0; i < k; ++i) {
std::pop_heap(heap.begin(), heap.end(), cmp);
const Point& top = heap.back();
std::cout << top.x << " " << top.y << std::endl;
heap.pop_back();
}
}``````

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

As suggested Euclidean distance can be used to find the nearest number in a given plan.

Distance between point (a,b) and (x,y) can be calculated as dist((x, y), (a, b)) = √(x - a)² + (y - b)²

``````public class EuclideanDistance {

public static void main(String[] args) {
int[][] points = {{1,2}, {4,5}, {-1,3}, {0,1}};
nearestTo00(points);
}

private static void nearestTo00(int[][] points) {
//Eucledian distance is given as dist((x, y), (a, b)) = √(x - a)² + (y - b)²
double dist = Double.MAX_VALUE;
int x = 0, y = 0;
for(int[] point: points) {
double currentDist = Math.sqrt(Math.pow(0-point,2) + Math.pow(0-point,2));
if(currentDist < dist) {
dist = currentDist;
x = point;
y = point;
}
}
System.out.println("Nearest Number: {" + x + " " + y + "}");
}
}

Output:
======
Nearest Number: {0 1}``````

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.