FastPrep
Problem · Tree

Equalize Server Latency

Learn this problem
● MediumTiktok logoTiktokOA
See Tiktok hiring insights

Problem statement

TikTok's server network is structured as a perfect binary tree with n servers, where servers are numbered from 0 to n-1. Each server is connected to its parent with the following configuration:

  • The parent of server i is floor((i-1)/2), for i > 1. Here, floor(x) denotes the greatest integer less than or equal to x
  • The children of server i are the servers numbered 2*i + 1 and 2*i + 2, if they exist
  • The root server (server 0) has no parent

    • The root server (server 0) handles requests, which are passed down to its child servers.

  • The latency cost between server i and its parent is defined as the time taken for data to travel along the edge between them and is given by latency[i-1] for i > 1
  • The latency from the root server to any leaf server is the sum of the latencies along the path from the root to that server

    • The goal is to ensure that the latency from the root to every leaf server is the same. Currently, latencies along different paths may vary. You are allowed to increase the latency of some connections but cannot decrease any latency. You have to find the minimum amount of additional latency needed to equalize the latency from the root to all leaf servers.

    Function

    minAdditionalLatency(n: int, latency: int[]) → int

    Complete the function minAdditionalLatency.

    minAdditionalLatency has the following parameters:

    • int n: the number of servers
    • int[] latency: an array of integers representing the latency costs

    Returns

    int: the minimum additional latency needed to equalize the latency from the root to all leaf servers

    Examples

    Example 1

    n = 7latency = [3, 1, 2, 1, 5, 4]return = 3
    Example 1 illustration
    The given arrangement should look like this: With latencies: We can increment the latencies as follows: - Incrementing edge latency[0] by 1. (Connecting nodes 0 and 1) - Incrementing edge latency[3] by 1. (Connecting nodes 1 and 4) - Incrementing edge latency[5] by 1. (Connecting nodes 2 and 6) After making the above increments, the cost from the node to each leaf node is equal to 6. Since we have made a total of 3 increments, the answer is 3. It can be shown that the answer cannot be less than 3 :)

    Example 2

    n = 3latency = [10, 5]return = 5
    Example 2 illustration
    Considering 0-based indexing, we can increment the latency for the connection between servers 0 and 2 by 5. After maing the increment, the distance from the root server to each leaf server will be equal to 10. Since we have made a total of 5 increments, the answer is 5. It can be shown that the answer cannot be less than 5 :)

    More Tiktok problems

    drafts saved locally
    public int minAdditionalLatency(int n, int[] latency) {
  // write your code here
}
    n7
    latency[3, 1, 2, 1, 5, 4]
    expected3
    checking account