Equalize Server Latency
Updated
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
iisfloor((i-1)/2), fori > 1. Here,floor(x)denotes the greatest integer less than or equal tox - The children of server
iare the servers numbered2*i + 1and2*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
iand its parent is defined as the time taken for data to travel along the edge between them and is given bylatency[i-1]fori > 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 serversint[] 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
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
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 interview questions
- Minimum Cost of Every K-Capable Model SetOA · Seen Nov 2026
- Longest Substring Without Repeating CharactersPHONE SCREEN · Seen Oct 2026
- Next Greater Indices and Maximum GapPHONE SCREEN · Seen Oct 2026
- Count Subarrays with at Least K Equal-Fruit PairsOA · Seen Oct 2026
- Shell Command Counts with History ReferencesOA · Seen Oct 2026
- Count Subarrays Matching a Comparison PatternOA · Seen Sep 2026
- Product Minus Sum of DigitsOA · Seen Aug 2026
- Count 2x2 Submatrices by Black CellsOA · Seen Aug 2026
- Find All Local PeaksOA · Seen Aug 2026
- Count Case-Insensitive TripletsOA · Seen Aug 2026
Similar questions at other companies
- Equalize Server LatencyMicrosoft · OAMicrosoft interview questions
- Binary Tree CamerasAmazon · OA · PHONE SCREEN
- Collect Opportunity Data in a TreeSalesforce · OASalesforce interview questions
- Collect CoinsCisco · OACisco interview questions
- Uber Circular Shuttle OptimizationUber · OAUber interview questions
- Minimum Flips to Match Expected Binary Values in a TreeUKG · OAUKG interview questions
- Save the UniverseRubrik · OARubrik interview questions
- Limit an Organization Tree's HeightRippling · PHONE SCREEN · ONSITE INTERVIEWRippling interview questions
- Count Prime Values in SubtreesVisa · OAVisa interview questions
- Minimum N-ary Tree Depth DeletionsSnowflake · OA · PHONE SCREENSnowflake interview questions
TikTok interview experiences
- TikTok AI Infra Intern LLM Round 2: 1 Experience
- TikTok AI Infra Intern DeepSpeed Round: 1 Experience
- TikTok AI Infra Intern Kernel Round: 1 Experience
- TikTok AI Infra Intern Interviews, 3 Rounds: 1 Experience
- TikTok AI Infra Intern Interview Timeline: 1 Experience
- TikTok AI Infra Intern Onsite Round 2: 1 Experience