Running Median of a Multilevel Linked List in Level Order
Updated
Problem statement
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 <= 1000next.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 (anextor achild) leading to it, and every node can be reached from node0.
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