FastPrep
Problem · Tree

Collect Opportunity Data in a Tree

Learn this problem
● HardSalesforce logoSalesforceOA
See Salesforce hiring insights

Problem statement

You are given an undirected tree with n nodes labeled from 0 to n - 1. The tree is defined by n - 1 edges.

Each node represents a branch office. You are also given a binary array opportunityData of size n, where:

  • opportunityData[i] = 1 means branch i contains important data.
  • opportunityData[i] = 0 means it does not.

You may start at any node. You can traverse edges in both directions. You must start and end at the same node.

Special Rule: When you are at a node, you can collect data from all nodes within distance <= 2 edges from your current location.

Return the minimum number of edges you must traverse to collect all important data.

Function

collectOpportunityDataInTree(n: int, edges: int[][], opportunityData: int[]) → int

Examples

Example 1

n = 10edges = [[0,1],[0,2],[0,5],[1,3],[1,4],[3,9],[5,6],[6,7],[7,8]]opportunityData = [0,0,1,1,0,0,0,0,1,1]return = 6

Nodes 2, 3, 8, and 9 contain important data.

One optimal strategy:

  • Start at node 1.
  • From node 1, collect data at 3 and 9 (within distance 2).
  • Travel to node 0 and collect 2.
  • Travel toward node 6 to collect 8.
  • Return to the starting node.

Total edges traversed = 6.

Constraints

  • 2 <= n <= 10^5
  • edges.length == n - 1
  • The input graph is a valid tree
  • opportunityData[i] is either 0 or 1

More Salesforce problems

drafts saved locally
public int collectOpportunityDataInTree(int n, int[][] edges, int[] opportunityData) {
  // write your code here
}
n10
edges[[0,1],[0,2],[0,5],[1,3],[1,4],[3,9],[5,6],[6,7],[7,8]]
opportunityData[0,0,1,1,0,0,0,0,1,1]
expected6
checking account