Meeting point for 5 people with least distance travelled (interview question) I had an interview today and I'm completely stumped on what they asked me. Essentially: if you are given 5 people on a 2D grid, and you need to meet at a point with the least amount of distance travelled, how would you calculate it?
What I had told the interviewer after some questions is to use the pythagorean theorem for every point and then add these together. I know I completely failed in answering...
Anyway, what is the proper way to do this? And is there a name for this type of problem so I can read more into it?
Thanks!
 A: Let's do it for a single dimension, X1 to X5 in ascending order.
X3 should be the meeting point.
If the meeting point X > X3 then you had 3 people going from X3 to X instead of 2 people from X to X3. With this principal you get that the best point is X3.  
The Y points should also be set in ascending order, which means that the person at X1 does not necessarily have to be at Y1.  
Similarly, Y3 is a good meeting point for the Y axis.  
I don't know whether X3,Y3 is the best point, but the answer is a good start for an interview.
A: Because you're on a grid, you can separate each person's motion into motion along the $x$-axis and motion along the $y$-axis; the amount of motion required is just the sum of these two components.  (This is the "Manhattan distance" or $L_1$-distance.)  So if you can simultaneously minimize the total $x$-distance that must be traveled (which depends only on the $x$-coordinate of the meeting place) and the total $y$-distance that must be traveled (which depends only on the $y$-coordinate of the meeting place), then you've found the optimal spot.  As pointed out in the other answer, in one dimension the optimal meeting place is always the median of the locations (or anywhere between the two middle locations, if the number of people is even).  So the correct answer here is $(\bar{x}, \bar{y})$, where $\bar{x}=\text{median}(\{x_i\})$ and $\bar{y}=\text{median}(\{y_i\})$.
