FastPrepRunning Median of a Multilevel Linked List in Level Order
Problems/Running Median of a Multilevel Linked List in Level Order

Running Median of a Multilevel Linked List in Level Order

Nutanix logoNutanix● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: In a 2025 Nutanix campus internship loop, the second interview began with a linked list whose nodes have both a next pointer and a child pointer. It asked for the nodes level by level. A later question in the same round asked for the running median of those values.

The report gives no input format, no examples and no rule for an even count. It does not spell out how the running median connects to the first question. Reading it as the running median of the level-order values is our interpretation. Here the list comes as three arrays with node 0 at the top. The child lists of a level are read in the order of their parent nodes. An even count uses the average of the two middle values. You return only the medians. The round also had a sorted version with a changed input, and a version of the first question built on the running median. Their details are not given, so they are not part of this problem.

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

A multilevel linked list has n nodes numbered from 0 to n - 1. Node i holds the number values[i] and two pointers: next[i] is the node after it in its own list, and child[i] is the first node of a separate list that hangs below it. A pointer of -1 means there is no such node. Node 0 is the first node of the top list.

Read the nodes in level order. The first level is the top list, read from node 0 along next pointers. Each later level is made of the child lists of the nodes in the level before it, taken in the order those nodes were read. Each child list is read from its first node along next pointers.

After reading each value, find the median of all the values read so far. With an odd count, it is the middle value after sorting. With an even count, it is the average of the two middle values.

Return an array with the median after each value, in reading order.

Function

levelOrderRunningMedians(values: int[], next: int[], child: int[]) → double[]

Examples

Example 1

values = [10,4,7,2,9,6,1]next = [1,2,-1,4,-1,-1,-1]child = [3,-1,5,6,-1,-1,-1]return = [10.0,7.0,7.0,5.5,7.0,6.5,6.0]

The top list is 0 → 1 → 2 with values 10, 4, 7. One child link down, node 0 starts the list 3 → 4 (values 2, 9) and node 2 starts the list made of node 5 (value 6). Two child links down, node 3 starts the list made of node 6 (value 1). So the level order is 10, 4, 7, 2, 9, 6, 1.

The running medians are: 10; the middle of 4 and 10 is 7; the middle of 4, 7, 10 is 7; for 2, 4, 7, 10 it is (4 + 7) / 2 = 5.5; for 2, 4, 7, 9, 10 it is 7; for 2, 4, 6, 7, 9, 10 it is (6 + 7) / 2 = 6.5; and for 1, 2, 4, 6, 7, 9, 10 it is 6.

Example 2

values = [-3]next = [-1]child = [-1]return = [-3.0]

There is one node, so the only running median is its value, -3.

Example 3

values = [-5,3,0,-2]next = [-1,2,-1,-1]child = [1,-1,3,-1]return = [-5.0,-1.0,0.0,-1.0]

The top list is only node 0 (value -5). Its child list is 1 → 2 (values 3, 0), and node 2 has the child list made of node 3 (value -2). The level order is -5, 3, 0, -2, and the running medians are -5, (-5 + 3) / 2 = -1, 0, and (-2 + 0) / 2 = -1.

Constraints

  • 1 <= values.length <= 1000
  • next.length == child.length == values.length
  • -10^9 <= values[i] <= 10^9
  • -1 <= next[i], child[i] <= values.length - 1
  • No pointer leads to node 0. Every other node has exactly one pointer (a next or a child) leading to it, and every node can be reached from node 0.

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
  • 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
  • Distance Sums to Special Nodes in a Weighted TreeONSITE INTERVIEW · Seen Aug 2021

Similar questions at other companies

  • Cheapest Flights Within K StopsAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • Find a Valid Course Completion OrderGoogle · ONSITE INTERVIEWGoogle interview questions
  • Zigzag Level-Order TraversalFlipkart · ONSITE INTERVIEW
  • Binary Tree Zigzag Level Order TraversalLinkedIn · PHONE SCREEN · ONSITE INTERVIEWLinkedIn interview questions
  • Binary Tree Zigzag Level Order TraversalMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Course Schedule IIWalmart · ONSITE INTERVIEWWalmart interview questions
  • Top View of a Binary TreeCapillary Technologies · ONSITE INTERVIEWCapillary Technologies interview questions
  • Task Order With PrerequisitesDoorDash · PHONE SCREEN · ONSITE INTERVIEWDoorDash interview questions
  • Course Schedule IIBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
  • Link a Binary Tree in Spiral OrderExpedia · ONSITE INTERVIEWExpedia 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 double[] levelOrderRunningMedians(int[] values, int[] next, int[] child) {
        // Write your code here.
    }
}
Checking account…