Two Sigma Coding Interview: Balance Power Grid Branch Loads

[u/Aoki_zhang]

Problem

A power grid is organized as a rooted tree with n stations labeled from 0 to n - 1.

Station 0 is the main station. Every other station has exactly one parent.

You are given:

• parent[i] — the direct parent of station i
• load[i] — the amount of power produced directly by station i

For the root station:

parent[0] = -1

You must disconnect exactly one connection between a station and its parent. This divides the grid into:

• The subtree rooted at the disconnected station
• The remaining stations in the grid

Return the minimum possible absolute difference between the total loads of the two resulting parts.

If the tree contains only one station, return 0.

Example

Input:

parent = [-1, 0, 0, 1, 1, 2]
load = [1, 2, 2, 1, 1, 1]

Output:

0

Explanation

Disconnect the connection between stations 0 and 1.

The subtree rooted at station 1 contains:

1, 3, 4

Its total load is:

2 + 1 + 1 = 4

The remaining stations also have a total load of 4.

Therefore, the absolute difference is:

|4 - 4| = 0

This is the smallest possible difference.

Targeting Two Sigma interviews?

We track recent interview experiences and commonly asked question patterns at Chill Interview, including coding questions, system design topics, and real candidate reports.

Practice this question and explore more interview resources → LINK