FastPrepDistance Sums to Special Nodes in a Weighted Tree
Problems/Distance Sums to Special Nodes in a Weighted Tree

Distance Sums to Special Nodes in a Weighted Tree

Nutanix logoNutanix● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A 2021 report from a virtual Nutanix campus loop for an MTS intern role describes a two-step tree question in the DSA round. The first step was the total distance from one chosen node of a weighted tree to all the other nodes. The follow-up named a group of nodes and asked which node has the least total distance to that group, and what that total is.

The report gives no input format, limits or tie rule. Here nodes are labeled 1 to n, and edges come as [a, b, w] with lengths from 1 to 10^6. Both answers are returned together in one array. The smallest label wins a tie. The candidate's follow-up idea, one search started from every node in the group, fits a nearest-node reading. This version follows the written definition instead, which adds up the distances.

Our version is about 85% the same as the reported question.

You are given a tree with n nodes labeled from 1 to n. Each edges[i] = [a, b, w] is an undirected edge of length w between node a and node b. The distance dist(u, v) is the total length of the edges on the path from u to v, and dist(u, u) = 0.

Part 1. Find the total distance from node x to all nodes, that is, the sum of dist(x, v) over every node v.

Part 2. You are also given special, a list of different nodes. The value of a node v is the sum of dist(s, v) over every node s in special. Find the smallest value any node has, and the node that has it. If several nodes share the smallest value, pick the one with the smallest label. Part 2 does not use x, and the best node does not have to be special.

Return the array [sum, node, value]: the Part 1 sum, then the Part 2 node and its value.

Function

specialNodeDistances(n: int, edges: int[][], x: int, special: int[]) → long[]

Examples

Example 1

n = 5edges = [[1,2,4],[2,3,1],[2,4,2],[4,5,3]]x = 1special = [3,5]return = [24,2,6]

Part 1: from node 1, the distances are 0 to node 1, 4 to node 2, 4 + 1 = 5 to node 3, 4 + 2 = 6 to node 4 and 6 + 3 = 9 to node 5. They add up to 24.

Part 2: the special nodes are 3 and 5, and the path between them is 3, 2, 4, 5 with length 1 + 2 + 3 = 6. Every node on that path is at distance 6 in total from the two special nodes, so nodes 2, 3, 4 and 5 all have a value of 6. Node 1 is off the path: it is 5 from node 3 and 9 from node 5, so its value is 14. The smallest value is 6, and the smallest label that reaches it is 2.

Example 2

n = 6edges = [[1,2,5],[1,3,5],[1,4,5],[4,5,1],[4,6,1]]x = 4special = [2,3,5]return = [27,1,16]

Part 1: from node 4, node 1 is 5 away, nodes 2 and 3 are 10 away, and nodes 5 and 6 are 1 away, so the sum is 5 + 10 + 10 + 1 + 1 = 27. Node 4 does not have to be special.

Part 2: the special nodes are 2, 3 and 5. Node 1 is 5 from node 2, 5 from node 3 and 6 from node 5, for a value of 16. Node 4 has 10 + 10 + 1 = 21, nodes 2 and 3 each have 0 + 10 + 11 = 21, node 5 has 11 + 11 + 0 = 22 and node 6 has 11 + 11 + 2 = 24. The best node is 1 with value 16, even though it is not special.

Example 3

n = 1edges = []x = 1special = [1]return = [0,1,0]

There is only one node. Its distance to itself is 0, so both the Part 1 sum and the smallest value are 0, at node 1.

Constraints

  • 1 <= n <= 10^4
  • edges.length == n - 1
  • edges[i].length == 3
  • 1 <= edges[i][0], edges[i][1] <= n
  • 1 <= edges[i][2] <= 10^6
  • The edges form a tree: every node can reach every other node.
  • 1 <= x <= n
  • 1 <= special.length <= n
  • 1 <= special[j] <= n
  • All values in special are different.

More Nutanix Onsite Interview questions

  • Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
  • Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
  • Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
  • Count Connected Components in an Undirected GraphONSITE INTERVIEW · Seen Aug 2025
  • LRU CacheONSITE INTERVIEW · Seen Aug 2025
  • Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
  • Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
  • Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
  • Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
  • Sudoku SolverONSITE INTERVIEW · Seen Feb 2022

Similar questions at other companies

  • Sum of Weighted Distances in a TreeGoogle · ONSITE INTERVIEWGoogle interview questions
  • Maximum Reservoir PowerWells Fargo · OAWells Fargo interview questions
  • Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
  • Maximum Strength of Every NeuronMicrosoft · OAMicrosoft interview questions
  • Tree Node With Maximum BeautyC3.ai · OAC3.ai interview questions
  • Filter Undesired Comments and Their DescendantsReddit · PHONE SCREEN · ONSITE INTERVIEWReddit interview questions
  • Delete and Compact a Forest SubtreePinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
  • Transitive Employee Referral CountsRobinhood · ONSITE INTERVIEWRobinhood interview questions
  • Aggregate Machine TopologyOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
  • Diameter of an Acyclic Undirected GraphSalesforce · ONSITE INTERVIEWSalesforce interview questions

Interview reports that mention this question

  • Nutanix Intern Debugging Round and Interviews: 25 Experiences

Nutanix interview experiences

  • Nutanix SWE Intern Phone Screens: 20 Experiences (Part 3 of 3)
  • Nutanix SWE Intern OA Questions: 16 Experiences (Part 2 of 3)
  • Nutanix U.S. SWE Intern Interviews: 54 Experiences (Part 1 of 3)
  • Nutanix SWE OA and Interviews, Level Not Reported: 9 Experiences
All Nutanix interview questionsSee Nutanix hiring insights
Saved
class Solution {
    public long[] specialNodeDistances(int n, int[][] edges, int x, int[] special) {
        // Write your code here.
    }
}
Checking account…