FastPrep
Problem · Tree

Collect Opportunity Data in a Tree

● HardSalesforceOA
See Salesforce hiring insights

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.

Examples
01 · Example 1
n = 11
edges = [[0,1],[0,2],[0,6],[1,3],[1,4],[3,10],[6,7],[7,8],[8,9]]
opportunityData = [0,0,1,1,0,0,0,0,0,1,1]
return = 6

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

One optimal strategy:

  • Start at node 1.
  • From node 1, collect data at 3 and 10 (within distance 2).
  • Travel to node 0 and collect 2.
  • Travel toward node 7 to collect 9.
  • 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
}
n11
edges[[0,1],[0,2],[0,6],[1,3],[1,4],[3,10],[6,7],[7,8],[8,9]]
opportunityData[0,0,1,1,0,0,0,0,0,1,1]
expected6
sign in to submit