How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Compute distance-sum from every tree node

Q: Compute distance-sum from every tree node

This question evaluates understanding of tree and graph algorithms, including computation of pairwise distances and techniques for aggregating path lengths across nodes.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

## Problem You are given an undirected tree with **n** nodes labeled `0..n-1` and a list of `n-1` edges. The tree is connected and contains no cycles. For each node `i`, compute: \[ ans[i] = \sum_{j=0}^{n-1} dist(i, j) \] where `dist(i, j)` is the number of edges on the unique path between nodes `i` and `j`. ## Input - Integer `n` - List `edges`, where each element is a pair `[u, v]` indicating an undirected edge between `u` and `v` ## Output - An integer array `ans` of length `n`, where `ans[i]` is the sum of distances from node `i` to all nodes. ## Constraints - `1 ≤ n ≤ 2 * 10^5` - `edges.length = n - 1` - `0 ≤ u, v < n` - The input graph is a tree. ## Example Input: - `n = 4` - `edges = [[0,1],[1,2],[1,3]]` Output: - `ans = [5,3,5,5]` Explanation: - From node `1`: distances to `[0,2,3]` are `[1,1,1]`, sum is `3`. - From node `0`: distances to `[1,2,3]` are `[1,2,2]`, sum is `5`.

Quick Answer: This question evaluates understanding of tree and graph algorithms, including computation of pairwise distances and techniques for aggregating path lengths across nodes.

You are given an undirected tree with n nodes labeled 0 to n-1 and a list of n-1 edges. The tree is connected and contains no cycles. For each node i, compute ans[i], the sum of distances from node i to every other node in the tree. Formally: ans[i] = sum(dist(i, j)) for all j from 0 to n-1, where dist(i, j) is the number of edges on the unique path between i and j. Your solution should run efficiently for large trees.

Constraints

1 <= n <= 2 * 10^5
edges.length == n - 1
0 <= u, v < n
The input graph is a tree: connected and acyclic
The answer for a node can exceed 32-bit signed integer range, so use 64-bit integers in fixed-width languages

Examples

Input: (1, [])

Expected Output: [0]

Explanation: A tree with one node has no other nodes to reach, so the distance sum is 0.

Input: (4, [[0, 1], [1, 2], [1, 3]])

Expected Output: [5, 3, 5, 5]

Explanation: From node 1, distances to 0, 2, and 3 are 1, 1, and 1, so the sum is 3. Each leaf has total distance 5.

Input: (5, [[0, 1], [0, 2], [0, 3], [0, 4]])

Expected Output: [4, 7, 7, 7, 7]

Explanation: Node 0 is connected directly to all others, so its sum is 4. Any leaf is distance 1 from node 0 and distance 2 from the other three leaves, giving 1 + 2 + 2 + 2 = 7.

Input: (6, [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]])

Expected Output: [15, 11, 9, 9, 11, 15]

Explanation: This is a straight line. Middle nodes have the smallest distance sums, and symmetric positions have equal answers.

Hints

Root the tree at any node, such as 0. In one traversal, compute each node's depth and the size of every subtree.
If you know the answer for node u, then for a child v: moving the root from u to v makes all nodes in v's subtree 1 closer and all other nodes 1 farther.

Quick Overview

This question evaluates understanding of tree and graph algorithms, including computation of pairwise distances and techniques for aggregating path lengths across nodes.