Minimum Town Sum Difference
Reported by candidates from Google's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The naive plan for this Google OA, reported in December 2025, is to delete each edge and rerun a traversal to sum both sides. That's O(n^2), and with n up to 10^5 it dies. The real problem is a tree with town counts on nodes, and you need the edge cut that splits the total as evenly as possible. It's a subtree-sum problem in disguise. If you blank on the traversal under pressure, StealthCoder is the safety net running invisibly during the live OA. But the idea is short enough to hold in your head tonight.
The problem
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 = 2 towns = [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 = 5 towns = [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.
Reported by candidates. Source: FastPrep
Pattern and pitfall
Root the tree at node 1 and compute the subtree sum for every node with one DFS. Total is the sum of all towns. Cutting the edge between a node and its parent gives components of size sub[v] and total - sub[v], so the difference is abs(total - 2*sub[v]). Take the min over every non-root node. The edge case that breaks naive code is recursion depth. A path-shaped tree with 10^5 nodes will overflow the stack in many languages, so use an iterative DFS or BFS order and accumulate sums in reverse. Also don't forget n = 1 has no edge to delete, though the constraints suggest you'll mostly see n >= 2. Build the adjacency list from roads, track parents instead of a visited set if you like, and keep sums in a wide integer. StealthCoder is the hedge if the iterative conversion trips you live.
Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.
You can drill Minimum Town Sum Difference cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Google's OA.
Google reuses patterns across OAs. Made by an engineer who treats the OA as theater. If yours is tonight, you don't have time to grind. You have time to hedge. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Minimum Town Sum Difference FAQ
What's the trick to Minimum Town Sum Difference?+
Compute every subtree sum once, then each edge cut is just a node and its parent. The two components are sub[v] and total minus sub[v]. Minimize abs(total - 2*sub[v]) across all non-root nodes. One pass, O(n) time.
How hard is this really?+
Medium. The idea is standard if you've seen subtree sums on trees. The difficulty is avoiding the O(n^2) brute force and handling deep trees at n up to 10^5 without blowing the recursion stack.
Why does recursion fail here?+
A chain-shaped tree can be 10^5 levels deep. Recursive DFS overflows the stack in several languages. Use an iterative DFS or BFS to get a traversal order, then process nodes in reverse so children add into parents.
Is this tree-sum pattern still asked at Google?+
It was reported in December 2025, so yes, treat it as live. The pattern of one DFS, aggregate subtree values, then evaluate each edge shows up in many tree OA questions with small twists.
How do I prepare in 48 hours?+
Write this once from scratch with an iterative traversal. Test a two-node tree, a star, and a long chain. Then practice the same shape with a different aggregate, like node counts. That covers most variants of this pattern.