Amazon VO 面试真题解析：连接所有数据中心的最小电缆长度

Given coordinates of data centers (an array of points on a 2D plane), find the minimum length of cable required to connect all data centers.

Example:

DC1 (0, 0)
DC2 (1, 0)
DC3 (0, 1)
DC4 (-1, 0)
DC5 (0, -1)

Possible solutions:

• Connect the four outer points through the center: cost = 4 (optimal)
• A non-optimal connection: cost = 2 * sqrt(2) + 2

这道题本质上是二维平面上的最小连通网络问题：给定若干数据中心坐标，要求用尽可能短的电缆把所有点连通。核心思路通常是把每个数据中心看成图中的节点，任意两点之间的连线长度就是欧几里得距离，然后用最小生成树（MST）来求总成本最小的连接方式。对于示例中的十字形点集，最佳方案是让中心点作为枢纽，把四个方向的点连接起来，总长度为 4，而不是把边直接拉成折线或菱形，那样会更长。