Google·Software Engineer·Onsite - Coding / Algorithms·Senior

SeniorPrefer not to say

May 2026

Summary

Google onsite coding round, one question the whole time. The problem was sum of distances in a tree and the interviewer wanted to see you walk through the brute force before jumping to the optimized solution. Pretty standard for Google but the re-root DP is one of those things you either know cold or you're fumbling through it live.

Questions Asked (1)

Given an undirected tree of N nodes, return an array where each entry is the sum of distances from that node to every other node in the tree.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The interviewer wanted the O(n²) baseline named and sketched out first, then the O(n) two-pass version.

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, then reroot the tree to compute the sum for all other nodes in O(N) time. Explain the rerooting technique clearly, emphasizing how the sum for a child can be derived from its parent's sum using subtree sizes.

Pro tip: Mention that this is a classic tree DP problem and that the O(N) solution is optimal; also discuss how you would handle large N (e.g., recursion depth) by using iterative DFS or increasing recursion limit.

1. Clarify and Define

Confirm the input format (adjacency list or edges) and output requirements. Define the problem: for each node, sum of distances to all other nodes.

2. Brute Force Baseline

Acknowledge that a naive BFS/DFS from each node would be O(N^2). This sets the stage for optimizing.

3. First Pass: Root the Tree

Pick an arbitrary root (e.g., node 0). Compute subtree sizes and the sum of distances from the root to all nodes using a post-order DFS.

4. Second Pass: Reroot DP

Use a pre-order DFS to compute the sum for each node from its parent: sum[child] = sum[parent] - size[child] + (N - size[child]).

5. Analyze Complexity and Edge Cases

State O(N) time and O(N) space. Discuss edge cases like N=1, skewed trees, and recursion depth.

Key Points to Mention

Two-pass DFS (post-order then pre-order) for O(N) time.
Subtree size computation and its role in rerooting.
Rerooting formula: sum[child] = sum[parent] - size[child] + (N - size[child]).
Time and space complexity: O(N) time, O(N) space.
Handling recursion depth for large N (iterative DFS or sys.setrecursionlimit).
Comparison with brute-force O(N^2) approach to highlight optimization.

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