Media.net SDE-1 interview coding question off campus 2021 graduate
Summary
I encountered a challenging tree problem during my Media.net SDE-1 interview, which required calculating the sum of distances from each node to all other nodes in a weighted binary tree with an O(N) time complexity.
Full Experience
During my off-campus interview for the SDE-1 role at Media.net, I was presented with a complex coding problem. The task involved a rooted binary tree where edges had weights. I needed to calculate the sum of distances from each node (SUM[u]) to all other nodes in the tree. Specifically, the problem had two parts: first, calculate SUM[root], and then calculate the entire SUM array for all nodes from 1 to N. An example was provided to illustrate the problem, and the expected time complexity was strictly O(N).
Interview Questions (1)
You are given a rooted binary tree with weights on edges. The distance between two nodes in this tree is the sum of the edge weights on the path between the two nodes. SUM[u] is the sum of the distances between u and all the other nodes in the tree.
Task 1: Calculate SUM[root]
Task 2: Calculate the array SUM for all nodes 1 to N.
Example :
1(root)
/(50) \(10)
2 3
(10)/ \(10) (30)/ \(20)
6 7 4 5
(3)/ \(4)
8 9Sum[1] = 377
Sum[2] = 327
Sum[6] = 277
....
Expected time complexity = O(N).
N = Number of node in given tree.