Software Engineer · Phone Screen · Coding

Google — Software Engineer ✅ Passed

Level: Unknown Level

Round: Phone Screen · Type: Coding · Difficulty: 6/10 · Duration: 60 min · Interviewer: Unfriendly

Topics: Tree Traversal, Depth-First Search (DFS), Breadth-First Search (BFS), Dynamic Programming, Re-rooting

Location: Mountain View, CA

Interview date: 2025-12-31

Summary

I was asked to find the sum of distances from each node to all other nodes in a given tree.

Details

The coding question I received was:

Given a tree, calculate the sum of the distances from each node to all other nodes.

My Approach:

1. Baseline (Non-Optimal):

   • I initially suggested performing a BFS/DFS from each node to calculate the sum of distances to all other nodes.
   • The time complexity for this approach is O(n^2), which guarantees correctness but would timeout for large n.
   • I mentioned that the tree structure should allow for optimization to O(n) using DP / rerooting.

2. Optimal Solution (Reroot DP, Two DFS):

   • The core idea involves arbitrarily selecting node 0 as the root and calculating:
     • sub[u] = size of the subtree rooted at u
     • dp[u] = sum of distances from all nodes in the subtree rooted at u to u
   • I performed a post-order DFS to compute these values:
     • dp[u] += dp[v] + sub[v] (because all nodes in subtree v are 1 unit further from u than from v)
   • After calculating these values, ans[0] = dp[0].
   • Then, I performed a pre-order DFS for rerooting, using the key formula:
     • When changing the root from u to its child v:
       • The sub[v] nodes in v's subtree are 1 unit closer, and the remaining n-sub[v] nodes are 1 unit further.
       • Therefore:
         • ans[v] = ans[u] - sub[v] + (n - sub[v]) = ans[u] + n - 2*sub[v]
   • This approach achieves an O(n) time complexity.

Key Insights:

• The interviewer appreciated my approach of first providing a naive solution to ensure correctness, then refining it to an optimal solution.

LeetCode similar: LeetCode 834