Special Nodes

Reported in interviews at Citadel

Problem statement

You are given a tree with N nodes labeled 1..N and N-1 undirected edges. A diameter of the tree is a longest path (measured in number of edges); a tree can have several diameters that share the same maximum length. A node is special if it is an endpoint of at least one diameter. Return an array of length N where position i (0-indexed, for node i+1) is 1 if node i+1 is special and 0 otherwise.

Implement:

def specialNodes(N, edges):

Here edges is a list of [a, b] pairs. The function returns a list of N integers (each 0 or 1).

Example: N = 7, edges = [[6,1],[7,1],[1,2],[2,3],[3,5],[3,4]]. The spine is 1-2-3, with 6 and 7 hanging off node 1 and 4 and 5 hanging off node 3. The four diameters are the paths between (6,5), (6,4), (7,5) and (7,4), each of length 4. The endpoints across all diameters are nodes 4, 5, 6, 7, so the answer is [0, 0, 0, 1, 1, 1, 1].

Another example: N = 2, edges = [[2,1]] returns [1, 1] (both nodes are diameter endpoints).

Show hint

How far is the farthest node from a given node, and how does that compare with the longest path in the tree?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems