Minimizing Sum of Absolute Deviations and Euclidean Distances

Reported in interviews at Citadel

Problem statement

Part 1. Given real numbers $x_1, \dots, x_n$, find the value $x_c$ that minimizes $\sum_{i=1}^{n} |x_c - x_i|$.

Part 2. Given $n$ points $d_i = (x_i, y_i)$ in the plane, find the point $p = (x_p, y_p)$ that minimizes $\sum_{i=1}^{n} \lVert p - d_i \rVert$, the sum of Euclidean distances to all the points.

Show hint

What does the sign of the derivative of each distance term tell you, as opposed to the derivative of a squared distance?

Relevant roles: Research Scientist, Applied Scientist and Data Scientist.

Related free problems