Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Google SWE coding round, one problem, tree stuff. The question was harder than it looked and I definitely underestimated how much graph theory I'd need to actually nail it cleanly.

Questions Asked (1)

Given an undirected connected tree with n nodes (labeled 0 to n-1) and n-1 edges, return an array where each element is the sum of distances from that node to every other node in the tree. An O(n) solution is expected.

Algorithms & Data Structures

Author's notes

I knew brute force was wrong the second I wrote it out.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a two-pass DFS approach: first compute subtree sizes and the sum of distances from the root to all nodes, then reroot the tree to compute the sum for every node in O(n) time. Explain the rerooting formula: when moving from parent to child, the sum changes by (n - 2*subtree_size[child]).

Pro tip: Emphasize that the rerooting technique avoids O(n^2) by reusing computations, and mention that this pattern generalizes to many tree DP problems. Also, clarify that the tree is connected and undirected, so the root can be chosen arbitrarily.

1. Clarify the problem and constraints

Confirm that the tree is connected and undirected, and that we need an O(n) solution. Discuss edge cases like n=1.

2. Choose a root and compute initial values

Pick any node (e.g., 0) as root. Perform a post-order DFS to compute subtree sizes and the sum of distances from the root to all other nodes.

3. Derive the rerooting formula

When moving the root from a parent to a child, the sum of distances changes by (n - 2 * subtree_size[child]). Explain why: nodes in the child's subtree get closer by 1, others get farther by 1.

4. Perform a pre-order DFS to compute all sums

Using the formula, compute the sum for each child from the parent's sum. Traverse the tree to fill the result array.

5. Analyze complexity and test

State that the algorithm runs in O(n) time and O(n) space. Walk through a small example to verify correctness.

Key Points to Mention

Two-pass DFS (post-order then pre-order) to achieve O(n) time.
Subtree size computation and its role in the rerooting formula.
The rerooting formula: sum[child] = sum[parent] + n - 2 * subtree_size[child].
Handling of edge cases such as n=1 (result is [0]).
Space complexity: O(n) for recursion stack and arrays.
Generalization: rerooting technique applies to other tree DP problems.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.