Media.net SDE-1 interview coding question off campus 2021 graduate
- Posted
- 1 Jul 2021
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.
How it went
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).
Questions asked (1)
- 01
Sum of Distances from Nodes in Weighted Binary Tree
Data Structures & Algorithms · Hard
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 arraySUMfor 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.