Connected Node Traversal with target distance
saiganesh_panchu
50
Interview

Given an "Node_iD, distance" map and nodeDependency map,

For all Node_iD in startingNodes Return list of all Node_iD's (entire tree nodes) if there are no branches emerging from starting node which has a branch_length > target_value
or Return Emptylist if atleast any one branch has branch_length > target_value

nodeDependecy_map = {1:[2], 2:[3,4], 3:[18], 4:[5], 5:[19], 19:[14,15,10], 14:[16], 15:[17], 10:[32], 32:[13], 13:[12], 12:[98], 200:[226,220], 226:[300], 220:[3] }
nodeLength_map = {1:20, 2:10, 3:23, 4:25, 5:30, 18:30, 19:40, 14:18, 15:10, 10:15, 16:24, 17:13, 32:18, 13:19, 12:23, 98:30, 200:30, 226:14, 220:26, 300:28}
startingNodes = [1, 200]

output when target value =200
For starting node 200 = [200,226,220,300,3,18] order doesnt matter
For starting node 1= [] as one of the branch has distance greater than target_value

output when target value = 300
For starting node 200 = [200, 226, 220, 300, 3, 18] order doesnt matter
For starting node 1= [1, 2, 3, 4, 18, 5, 19, 14, 15, 10, 16, 17, 32, 13, 12, 98]

image

whats the optimized solution for this problem ?

Comments (0)