media.net logo
Media.net· SDE-1

Media.net SDE-1 interview coding question off campus 2021 graduate

Posted
1 Jul 2021
295 reads

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)

  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 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   9

    Sum[1] = 377
    Sum[2] = 327
    Sum[6] = 277
    ....

    Expected time complexity = O(N).
    N = Number of node in given tree.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Media.net recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!