FastPrep
Problem · Tree

Maximum Strength of Every Neuron

Learn this problem
● HardMicrosoftFULLTIMEOA
See Microsoft hiring insights

Problem statement

You are given a tree-shaped network of n neurons with n - 1 undirected connections. Connection i joins neurons neuronFrom[i] and neuronTo[i]; neuron labels are 1-based.

Each neuron is either strong or weak:

  • strongConnectivity[i] = 1 means neuron i + 1 is strong and contributes +1.
  • strongConnectivity[i] = 0 means neuron i + 1 is weak and contributes -1.

The score of a connected subnetwork is the number of strong neurons in it minus the number of weak neurons in it.

Return an array neuronStrengths of length n, where neuronStrengths[i] is the maximum score among all connected subnetworks that contain neuron i + 1.

What the interview report shared

The report gave the tree model, complete scoring rule, and one concrete example. This practice version is an estimated 95% match to that core task; the report did not include numeric limits, so none are added here.

Function

maximumNeuronStrength(n: int, neuronFrom: int[], neuronTo: int[], strongConnectivity: int[]) → int[]

Examples

Example 1

n = 4neuronFrom = [1,1,1]neuronTo = [2,3,4]strongConnectivity = [0,0,1,0]return = [0,-1,1,-1]

Neuron 3 is strong, so the best connected subnetwork containing it has score 1. Neuron 1 can include neuron 3 for score 0. For either weak leaf, adding the center and the strong neuron still gives score -1, so its best strength is -1.

More Microsoft problems

drafts saved locally
public int[] maximumNeuronStrength(int n, int[] neuronFrom, int[] neuronTo, int[] strongConnectivity) {
    // write your code here
}
n4
neuronFrom[1,1,1]
neuronTo[2,3,4]
strongConnectivity[0,0,1,0]
expected[0,-1,1,-1]
checking account