FastPrep
Problem · Tree

Special Diameter Endpoints

Learn this problem
● HardMicrosoftOA
See Microsoft hiring insights

Problem statement

Given a tree with tree_nodes nodes numbered from 1 to tree_nodes, call a node special if it is an endpoint of at least one diameter of the tree.

The diameter of a tree is the number of edges in a longest path. Return a binary array with one value per node: 1 if the node is special, otherwise 0.

  2
 / \
1   3

Example tree: the diameter is the path 1 – 2 – 3.

Function

isSpecial(tree_nodes: int, tree_from: int[], tree_to: int[]) → int[]

Examples

Example 1

tree_nodes = 3tree_from = [2,2]tree_to = [1,3]return = [1,0,1]

The tree contains edges 2-1 and 2-3. Its unique diameter is the path from node 1 through node 2 to node 3, so nodes 1 and 3 are special and node 2 is not.

Constraints

  • 1 ≤ tree_nodes ≤ 10^5
  • 1 ≤ tree_from[i], tree_to[i] ≤ tree_nodes

More Microsoft problems

drafts saved locally
public int[] isSpecial(int tree_nodes, int[] tree_from, int[] tree_to) {
  // write your code here
}
tree_nodes3
tree_from[2,2]
tree_to[1,3]
expected[1,0,1]
checking account