Facebook Interview Question
Web DevelopersCountry: United States
Interview Type: Phone Interview
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.
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+" )";
}
}
}
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;
}
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();
}
}
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]);
}
}
}
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
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
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][0]*points[i][0] + points[i][1]*points[i][1];
if (distances.size() == k && distances.peek().distance > distance) {
distances.poll();
distances.add(new Node(i, distance));
} else if (distances.size() < k) {
distances.add(new Node(i, distance));
}
}
while (!distances.isEmpty()) {
Node n = distances.poll();
result.add(points[n.index]);
}
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));
});
}
}
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();
}
}
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}
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))
- adr August 20, 2018Solution 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.