FastPrepFlatten a Multilevel Singly Linked List

Flatten a Multilevel Singly Linked List

Bloomberg LP logoBloomberg LP● MediumNEW GRADPHONE SCREENONSITE INTERVIEW
Learn

Problem statement

Node i has value values[i], next index next[i], and child index child[i]; -1 means null. Starting at head, flatten the multilevel singly linked list in depth-first preorder by splicing every child list between its parent and the parent's original next continuation.

Return flattened values. Use O(1) auxiliary pointer state, excluding the returned array.

Function

flattenMultilevelSingly(values: int[], next: int[], child: int[], head: int) → int[]

Examples

Example 1

values = [1,2,3,4,5]next = [1,2,-1,4,-1]child = [-1,3,-1,-1,-1]head = 0return = [1,2,4,5,3]

Node 2's child list 4,5 is spliced before node 3.

Constraints

  • The pointer structure is finite and contains each reachable node once.
  • All nonnegative indices are valid.

More Bloomberg LP problems

See Bloomberg LP hiring insights
public int[] flattenMultilevelSingly(int[] values, int[] next, int[] child, int head) {
  // Write your code here.
}
values[1,2,3,4,5]
next[1,2,-1,4,-1]
child[-1,3,-1,-1,-1]
head0
expected[1,2,4,5,3]
Checking account…