## Facebook Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: In-Person

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

the question is simple. you need to know the guessing pattern. If not available the best way is to think of it as finding the average of the cluster of the sample points given after identifying the outliers. To find these clusters use a density based clustering algorithm. If a single cluster is formed, print its mean, but if there is more than 1 clusters are found the number could be the centroid of any of these clusters. Hence, in case of more clusters the result will not necessarily give you the right answer.

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

What kind of guesses? How were these guesses formed?

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

Good.

You need to know the underlying distribution of the guessing process.

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

How about just taking the averages? If there are n given points (x', y') = (sum(x)/n, sum(y)/n).

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

I believe it could be solved by Expectation Maximization method.

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

fentoyal -- I wrote the answer in the name field.

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

Center of mass...implies some kind of weighting. How would you derive such, or is every point weighted the same? In that case, your answer is no different from that of the person who suggested taking the average. I still think that the only reasonable answer based on what's given in the question is to ask "well, what's the distribution of the guessing process?"

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

best guess is the average point
x'=sum of all xs divided by the number of points
y'=sum of all ys divided by the number of points

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

maybe we can firstly find the mean using k-means, then calculate the average distance among all other points and the mean?

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

You can mathematically prove that the optimal solution is [sum(x)/n , sum(y)/n].

I just can't figure out a way to type it out here though. Let me give it a try

You can try to minimize summation((x-x')^2) + summation((y-y')^2) and take partial derivatives on x and y. You get 2 equations. Upon solving them you get the optimal solution to be what is mentioned above.

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

I don't think average is going to work. Consider this: let's simplify the problem to 1D and let's assume each guess has the answer "the point you are searching for is to the {left, right} relative to your guess".

Let's say the hidden point is at x=14. These are my guess, answer pairs:
0, to-the-right
1, to-the-right
3, to-the-right
7, to-the-right
15, to-the-left (ok, now I know it's (7..15) let's switch to binary search)
11, to-the-right
13, to-the-right
14, found-it!

If you take the average of these guesses then you are far from the actual point we were searching for.

If you look at these points and assume that they were guessed based on the above method then the best guess is the LAST guess. If you can recreate the guessing process then it can be found.

How can you recreate? Start at the left/right-most point, then take points one-by-one as long as distance increases exponentially. If 2^i distance stops being true then you reached the part where binary search kicks in. You do binary search along the remaining point as long as any point remains. If no point remains then that was the last point. That's the best guess.

In general the whole solution depends on how the guesses are made and what responses you receive for them.

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

We can find the best guess by finding the distance between two points.
1) Take original point (x,y)
2) Now take first point from points set, say (x1, y1)
3) Now calculate the distance between (x, y) and (x1, y1).
4) Store the distance and first point.
5) Now take second coordinate and find distance between original point (x,y)
6) If second distance is smaller then store second point distance and second point.

Similarly iterate on all points to find best approximate point.

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

The whole point of this question is that you don't have original point x, y

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

Typical machine learning regression problem.
You can use a bunch of method like Linear regression or Neuron Network.

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.