Facebook Interview Question for Web Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 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.

- adr August 20, 2018 | Flag Reply
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());
            list.add(tmp);
        }
        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+" )";
        }
    }
}

- PeyarTheriyaa August 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 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.

- DR adm August 22, 2018 | Flag Reply
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;
}

- mrz August 28, 2018 | Flag Reply
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));

points.forEach(i-> queue.add(i));

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);

}

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

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

- Delwar September 02, 2018 | Flag Reply
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[]>();

        list.add(new int[]{2,3});
        list.add(new int[]{2,4});
        list.add(new int[]{5,6});
        list.add(new int[]{8,6});
        list.add(new int[]{1,0});

        // 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)[0]*list.get(i)[0] + list.get(i)[1]*list.get(i)[1], 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++) {
            out.add(list.get(i));
        }

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

- CJ September 15, 2018 | Flag Reply
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

- Anonymous September 25, 2018 | Flag Reply
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[0]
        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[0], p[1]) for p in points] # we populate an array of distances

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

- Fabricio September 27, 2018 | Flag Reply
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[0],2) + Math.pow(0-point[1],2));
			if(currentDist < dist) {
				dist = currentDist;
				x = point[0];
				y = point[1];
			}
		}
		System.out.println("Nearest Number: {" + x + " " + y + "}");
	}
}

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

- Saurabh August 20, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More