FastPrep
Problem · Graph

TikTok Server Network Optimization

Learn this problem
● MediumTiktokINTERNOA
See Tiktok hiring insights

Problem statement

TikTok has installed n servers on a grid. Server j is located at (x[j], y[j]).

The cost of directly connecting servers i and j is:

min(|x[i] - x[j]|, |y[i] - y[j]|)

Build a network in which every server can communicate with every other server, either directly or through intermediate servers. Return the minimum possible total connection cost.

Function

minCostToConnectServers(x: int[], y: int[]) → int

Examples

Example 1

x = [2, 4, 8]y = [6, 10, 9]return = 3

To connect the servers, here's the strategy:

  1. Connect the first and second servers: The servers are at (2, 6) and (4, 10). The cost is calculated as min(|2 - 4|, |6 - 10|) = 2.
  2. Connect the second and third servers: The servers are at (4, 10) and (8, 9). The cost is min(|4 - 8|, |10 - 9|) = 1.
  3. Connect the first and third servers: The servers are at (2, 6) and (8, 9). The cost is min(|2 - 8|, |6 - 9|) = 3. However, we already have a cheaper way to connect them indirectly through the second server.

So, the optimal way to connect the first and second servers for 2, and then the second and third servers for 1. Thus, the total minimum cost is 2 + 1 = 3.

Constraints

  • 2 ≤ n ≤ 10^5
  • x.length = y.length = n
  • 0 ≤ x[i], y[i] ≤ 10^9
  • Multiple servers may have the same coordinates.

More Tiktok problems

drafts saved locally
public int minCostToConnectServers(int[] x, int[] y) {
  // write your code here
}
x[2, 4, 8]
y[6, 10, 9]
expected3
checking account