Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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?"
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.
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.
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.
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