FastPrepMinimum Town Sum Difference
Problems/Minimum Town Sum Difference

Minimum Town Sum Difference

Google logoGoogleFULLTIMEOA

Updated Sep 2026

QuestionFunctionExamplesConstraints

Problem statement

You are given a tree with n nodes numbered from 1 to n and n - 1 bidirectional edges. Node i + 1 has towns[i] towns.

Delete exactly one edge. This splits the tree into two connected components.

Return the minimum possible absolute difference between the total number of towns in the two resulting components.

Function

minTownsDiff(n: int, towns: int[], roads: int[][]) → int

Examples

Example 1

n = 2towns = [10,20]roads = [[1,2]]return = 10

Deleting the only edge creates components with sums 10 and 20, so the difference is 10.

Example 2

n = 5towns = [1,2,3,4,5]roads = [[1,2],[1,3],[3,4],[3,5]]return = 5

Deleting edge [1,3] gives component sums 12 and 3, difference 9. Deleting edge [3,5] gives sums 5 and 10, difference 5, which is minimum.

Constraints

  • 1 <= n <= 10^5
  • towns.length == n
  • 1 <= towns[i] <= 10^4
  • roads.length == n - 1
  • roads forms a tree.

More Google Online Assessment questions

  • Book Reading EveningsOA · Seen Nov 2026
  • Count Score CategoriesOA · Seen Nov 2026
  • Minimum Cars for Rental RequestsOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Shortest Path in a Binary MatrixOA · Seen Nov 2026
  • Robot Assembly Line ConflictsOA · Seen Oct 2026
  • Assign LockerOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
  • Biggest Number From DigitsOA · Seen Oct 2026
  • Consolidate On-Call RotationsOA · PHONE SCREEN · Seen Oct 2026
  • Decreasing SubsequencesOA · Seen Sep 2026
  • Minimize Absolute Difference of Server LoadsOA · Seen Sep 2026

Interview reports that mention this question

  • Google OA: What It Tests (2026)

Google interview experiences

  • Google L5 Security Engineer Domain Knowledge Round: 1 Experience
  • Google Software Engineer Onsite Questions: 10 Experiences
  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public int minTownsDiff(int n, int[] towns, int[][] roads) {
      // write your code here
    }
}
Checking account…