Facebook Interview Question for Software Engineer / Developers


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.

- Saurabh Khanduja January 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

What kind of guesses? How were these guesses formed?

- eugene.yarovoi January 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good.

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

- Anonymous January 16, 2012 | Flag
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).

- vijay January 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I believe it could be solved by Expectation Maximization method.

- Anonymous January 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- To calculate the mass center is enough January 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?"

- eugene.yarovoi January 17, 2012 | Flag
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

- MiKL~ February 13, 2012 | Flag Reply
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?

- javabean March 08, 2012 | Flag Reply
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.

- Mean square approach April 15, 2012 | Flag Reply
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.

- Safi December 11, 2014 | Flag Reply
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.

- Dhiraj Girdhar January 16, 2012 | Flag Reply
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

- eugene.yarovoi January 17, 2012 | Flag
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.

- dingdinghzq January 16, 2012 | 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