Menu
I was asked following question in interview recently:
Let suppose you have, following grid on Cartesian coordinate system ( Quadrant I).
o - x - x - x - o
| | | | |
x - x - x - o - x
| | | | |
x - o - o - x - x
where, o => person at intersection and x => no person at intersection
class Point {
int x;
int y;
boolean hasPerson;
}
Point findNearestPointWhereAllPeopleCanMeet(Point[] people) {
}
Implement a routine where given a list of people location (points), find a location(point) such that is closest point to all given point.
How would you solve this problem ?
1) Approach is k-d tree, but do you know any other solution ?
298
The shortest distance from a point to a plane is along a line perpendicular to the plane. Therefore, the distance from point P to the plane is along a line parallel to the normal vector, which is shown as a gray line segment.
Closest point from origin will be the perpendicular distance from origin to the line. We need to find an equation of the perpendicular from (0,0) on y = 2x + 3.
The brute force method of finding the nearest of N points to a given point is O(N) -- you'd have to check each point. In contrast, if the N points are stored in a KD-tree, then finding the nearest point is on average O(log(N)) .
If the problem calls for minimizing the Manhattan distance (that is, people only walk parallel to the axes), then the problem is then pretty trivial. First, selecting the x coordinate and the y coordinate are independent problems.
Then, for the each coordinate, simply find the median value of the position of the people along that axis. For many configurations of people, there can be more than one point that minimizes the sum of the walking distances of all people. (Just consider 2 people separated by more than 2 blocks in x and at the same y coordinate; any intersection in between will require the same total walking by the two people.)
If the problem calls for minimizing the Euclidean distance, then the goal is to find the 2-variable L1 median. This is a standard problem, but it is far from trivial. (See here, for instance.) There is a unique answer. Given that this was an interview question, I suspect that this does not apply.
150
Before going to study k-d trees these are some thoughts that came to my mind:
E.G. Given Point(0,0):
The MAX_distance for (0,0) is 6. Given your input the lowest MAX_distance should be 3 and there are many Points with that value like (2,1) for instance.
There should be ways to make this algorithm more efficient.. Maybe with k-d trees :p or with other tweaks like checking the total number of people, their relative location/distance, the MAX_distance value at any iteration, etc..
45
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
