Google Interview Question Help | Onsite 1

Round 1

Questions: Given a binary tree, with each edge having a cost associated. We want to cut the edges in such a way that all the leaf nodes get disconnected from the root which is 6. Find the minimum cost.

Example 1:

      6
    /   \ 
   4     2
  /
 1

• Weight 6 - 4 = 5
• Weight 6 - 2 = 2
• Weight 4 - 1 = 1

The answer should be 3 (we will remove edge 4-1 & 6-2 so that all leaf nodes are disconnected from the root which is 6).

Example 2:

• 6 - 3: Cost 4
• 6 - 5: Cost 2
• 3 - 7: Cost 3
• 3 - 8: Cost 5
• 5 - 4: Cost 1

The answer is 5 (In this case, you have to disconnect edge 5-4 & 6-3 to get minimum cost).