Facebook Interview Question for Software Engineer Interns


Country: UK
Interview Type: Phone Interview




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

We can solve it

1- FInd the distance of each point from center- O(n)
2- Sort the distance array and output k element- O(nlogn)

Second point can be reduced to O(nlogk), by using heap of size k.
Hence total time complexity is O(nlogk) with heap

- azambhrgn May 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If you're computing distance as euclidean distance, I believe you don't have to square root each calculation. I could have a lambda function for comparing distances like this:

{{
// C++
[](std::pair<int, int>& f, std::pair<int, int>& s) {
int first = pow(f.first, 2) + pow(f.second, 2);
int sec = pow(s.first, 2) + pow(s.second, 2);
return first < second;
}
}}

To sort the list of points.

- Jaftem May 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Does kd tree also serves the purpose here?

- PraTrick May 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Guys, use heap.
[ en.wikipedia.org/wiki/Heap_(data_structure) ]
You should be good to go. Get a k-heap, distance metric is Euclidean, I guess everyone knows that - and you should be good.
The code is so so trivial.
In Java, use a [ docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html ]

- NoOne May 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. O(k * n). We can go k times through the array. For i-th closest point, we find the closest point out of points i throug n. The closest point gets swapped with i-th point.
2. O(log k * n). We can use a heap (the code below).
3. Aa preprocessing, we can insert all of the points into a structure like R-Tree. Finding k closest point would be taking expected O(log n).

vector<Point> Closest(vector<Point> const &a, Point const &origin, int k)
{
	vector<Point> closest;
	if (a.size() >= k &&
		k > 0)
	{
		priority_queue<PQEntry> pq;
		for (int i = 0; i < a.size(); ++i) {
			double dx = origin.x_ - a[i].x_;
			double dy = origin.y_ - a[i].y_;
			double distance = dx * dx + dy * dy;
			bool insert = false;
			if (i < k) {
				insert = true;
			} else if (distance < pq.top().distance_) {
				pq.pop();
				insert = true;
			}
			if (insert) {
				pq.push(PQEntry(i, distance));
			}
		}
		while (!pq.empty()) {
			closest.push_back(a[pq.top().point_idx_]);
			pq.pop();
		}
	}
	return closest;
}

- Alex May 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My python solution

import math

a = [(1,2),(8,9),(10,11),(3,2),(0,1),(4,4)]
b = []
k = 2

for i,elem in enumerate(a):
	x = elem[0]
	y = elem[1]
	b.append((i,math.sqrt(math.pow(x,2)+math.pow(y,2))))

b.sort(key=lambda x : x[1])
print b

for i in range(k):
	print a[b[i][0]]

- nunziomeli5 May 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The best known algorithm that uses fast-selection is in O(n).
1. compute the distance of the points with the origin.
in order to find the k-smallest values, use the k-selection version that at every iteration the pivot is the median.
Please note that you need to use the fast-median algorithm (that partitions the data in groups of size 5 and uses the median of median ....)
Thus the running-time is:
T(n) = T(n/2)+ O(n)
--> T(n) = O(n)

Another way of implementation (to get rid of median finding) is to use randomized k-selection. I.e., shuffle the distances first and then follow the regular k-selection.
The EXPECTED running time of the algorithms is O(n)

--
p.s.: using the k-heap should be fast in practice.

- a.asudeh May 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C# solution

class Point{
        private int x;
        private int y;
        private double distance;
        public int X { get { return x; } set { x = value; } }
        public int Y { get { return y; } set { y = value; } }
        public double Distance { get { return distance; }}
        public Point(int x, int y){
            this.x = x;
            this.y = y;
            this.distance = Math.Sqrt(Math.Pow(x, 2) + Math.Pow(y, 2));
        }
        public static Point[] KClosest(Point[] points, int k){
            if (points.Count() <= k) { return points; }
            Point[] closest = new Point[k];
            Array.Sort(points, (Point x, Point y) => x.Distance.CompareTo(y.Distance));
            Array.Copy(points,closest,k);
            return closest;
        }
    }

- gmgarcia July 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my C# solution

class Point{
        private int x;
        private int y;
        private double distance;
        public int X { get { return x; } set { x = value; } }
        public int Y { get { return y; } set { y = value; } }
        public double Distance { get { return distance; }}
        public Point(int x, int y){
            this.x = x;
            this.y = y;
            this.distance = Math.Sqrt(Math.Pow(x, 2) + Math.Pow(y, 2));
        }
        public static Point[] KClosest(Point[] points, int k){
            if (points.Count() <= k) { return points; }
            Point[] closest = new Point[k];
            Array.Sort(points, (Point x, Point y) => x.Distance.CompareTo(y.Distance));
            Array.Copy(points,closest,k);
            return closest;
        }
    }

- gmgarcia July 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C# solution

class Point{
        private int x;
        private int y;
        private double distance;
        public int X { get { return x; } set { x = value; } }
        public int Y { get { return y; } set { y = value; } }
        public double Distance { get { return distance; }}
        public Point(int x, int y){
            this.x = x;
            this.y = y;
            this.distance = Math.Sqrt(Math.Pow(x, 2) + Math.Pow(y, 2));
        }
        public static Point[] KClosest(Point[] points, int k){
            if (points.Count() <= k) { return points; }
            Point[] closest = new Point[k];
            Array.Sort(points, (Point x, Point y) => x.Distance.CompareTo(y.Distance));
            Array.Copy(points,closest,k);
            return closest;
        }

}

- gmgarcia July 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My C# solution

class Point{
        private int x;
        private int y;
        private double distance;
        public int X { get { return x; } set { x = value; } }
        public int Y { get { return y; } set { y = value; } }
        public double Distance { get { return distance; }}
        public Point(int x, int y){
            this.x = x;
            this.y = y;
            this.distance = Math.Sqrt(Math.Pow(x, 2) + Math.Pow(y, 2));
        }
        public static Point[] KClosest(Point[] points, int k){
            if (points.Count() <= k) { return points; }
            Point[] closest = new Point[k];
            Array.Sort(points, (Point x, Point y) => x.Distance.CompareTo(y.Distance));
            Array.Copy(points,closest,k);
            return closest;
        }
    }

- gmgarcia July 21, 2017 | 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