Equalize Server Latency
Updated
Problem statement
A data center has n servers numbered 0 to n - 1, linked in a binary tree whose levels are all completely filled. Server 0 sits at the top. For every server v, its children (when they exist) are servers 2v + 1 and 2v + 2, and every server v > 0 hangs below server (v - 1) / 2 rounded down.
Every link from a server up to the server above it has a latency. The array latency has n - 1 values, and latency[j] is the delay on the link above server j + 1.
A request travels down from server 0 to a leaf server, and its total latency adds up every link it crosses. You want every such top-to-leaf route to have the same total. You may raise any link by any whole amount, but you may never lower one.
Return the smallest possible total amount of latency added across all links. Return it as a 64-bit integer.
Function
minExtraLatency(n: int, latency: int[]) → longExamples
Example 1
n = 7latency = [2,1,3,4,1,2]return = 5Server 1 leads to servers 3 and 4 over links of 3 and 4, so raise the link to server 3 by 1. Server 2 leads to servers 5 and 6 over links of 1 and 2, so raise the link to server 5 by 1. Now every path below server 1 is 4 and every path below server 2 is 2. From the root, the left side totals 2 + 4 = 6 and the right side totals 1 + 2 = 3, so raise the link to server 2 by 3. All four root-to-leaf paths now have latency 6, and the total added is 1 + 1 + 3 = 5.
Example 2
n = 3latency = [5,5]return = 0Both leaves are already 5 away from the root, so nothing is added.
Example 3
n = 3latency = [1,4]return = 3The paths are 1 and 4. Raising the link to server 1 by 3 makes both 4, so the answer is 3. Lowering the 4 is not allowed.
Constraints
3 <= n <= 2047, andn + 1is a power of two, so every level of the tree is full and its height is at most 10.latency.length == n - 11 <= latency[j] <= 10^9
More Microsoft Online Assessment questions
- Minimum Cost to Process Priority TasksOA · Seen Nov 2026
- Most Visited Sprint MarkerOA · Seen Nov 2026
- Maximum Escape Game ScoreOA · Seen Nov 2026
- Count Subarrays with a Perfect-Square ProductOA · Seen Nov 2026
- Maximum Interactive Team SizeOA · Seen Nov 2026
- Maximize Pipeline Throughput Under a Scaling BudgetOA · Seen Nov 2026
- Minimum Cost K-Capable ModelsOA · Seen Nov 2026
- Find Available Meeting RoomsOA · Seen Oct 2026
- Maximum Sum of a K-StarOA · Seen Oct 2026
- Capacity to Ship Packages Within DaysOA · ONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Equalize Server LatencyTikTok · OATikTok 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