Flatten a Linked List with Nested Side Branches into One Doubly Linked List
Company: Tesla
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
A singly linked list becomes a doubly linked list once every node also links back to its predecessor. This problem extends that conversion. Besides its forward link, any node may carry at most one **side branch**: a link to the first node of another list. Nodes inside a branch list may carry side branches of their own, so the whole structure is shaped like a binary tree whose root is the head of the main list.
Flatten the structure into one doubly linked list by splicing every side branch in between its parent node and the node that originally followed the parent. Branches nested inside a branch are spliced in the same way, before the rest of the enclosing branch continues.
The nodes are stored in two arrays. Nodes are labeled `0` to `n - 1`, and node `0` is the head of the main list. `next_node[i]` is the node that follows node `i` in its own list, or `-1` if node `i` is the last node of its list. `branch[i]` is the first node of node `i`'s side branch, or `-1` if node `i` has no side branch.
Return the flattened doubly linked list as two arrays of length `n`: `result[0][i]` is the node that comes after node `i` in the flattened list (`-1` for the last node), and `result[1][i]` is the node that comes before node `i` (`-1` for node `0`).
### Function Signature
```python
def flatten_with_branches(next_node: list[int], branch: list[int]) -> list[list[int]]:
```
### Rules
- In the flattened list, every node is immediately followed by the flattened contents of its side branch, if it has one, and after that by the flattened remainder of the list that originally followed it.
- Node `0` is the first node of the flattened list, and every node appears in it exactly once.
- If no node has a side branch, the flattened list is the main list in its original order, now with backward links. This is the plain singly-to-doubly conversion.
- Side branches do not appear in the output: after flattening, nodes are connected only by their forward and backward links.
- Return exactly two arrays: forward links first, backward links second.
### Constraints
- `1 <= n <= 100000`, where `n = len(next_node) = len(branch)`
- `-1 <= next_node[i] <= n - 1` and `-1 <= branch[i] <= n - 1`
- Node `0` is referenced by no entry of `next_node` or `branch`. Every other node is referenced by exactly one entry across the two arrays, and every node can be reached from node `0` by following `next_node` and `branch` links. The structure therefore has no cycles and no shared nodes.
- Branches may be nested, and the nesting depth can be as large as `n - 1`.
- The output is uniquely determined by the input.
### Examples
**Example 1**
- Input: `next_node = [1, 2, -1]`, `branch = [-1, -1, -1]`
- Output: `[[1, 2, -1], [-1, 0, 1]]`
- Explanation: There are no side branches. The list `0 -> 1 -> 2` keeps its order and gains backward links.
**Example 2**
- Input: `next_node = [1, 2, -1, 4, -1, -1]`, `branch = [-1, 3, -1, 5, -1, -1]`
- Output: `[[1, 3, -1, 5, 2, 4], [-1, 0, 4, 1, 5, 3]]`
- Explanation: The main list is `0 -> 1 -> 2`. Node `1` has the side branch `3 -> 4`, and node `3` has the side branch `5`. The flattened list is `0 -> 1 -> 3 -> 5 -> 4 -> 2`: node `3`'s branch comes right after node `3`, then the rest of node `1`'s branch (node `4`), then the rest of the main list (node `2`).
**Example 3**
- Input: `next_node = [1, -1, 3, -1]`, `branch = [-1, 2, -1, -1]`
- Output: `[[1, 2, 3, -1], [-1, 0, 1, 2]]`
- Explanation: Node `1` is the last node of the main list and has the side branch `2 -> 3`, so the branch simply extends the list: `0 -> 1 -> 2 -> 3`.
Overview: A linked list whose nodes may each carry one side branch, with branches nested like a binary tree, must be flattened into a single doubly linked list with every branch spliced between its parent and the parent's original successor. It tests pointer rewiring, ordering rules for nested branches, and handling very deep nesting.
Read the full Tesla Software Engineer interview experience this question came from
A singly linked list becomes a doubly linked list once every node also links back to its predecessor. This problem extends that conversion. Besides its forward link, any node may carry at most one **side branch**: a link to the first node of another list. Nodes inside a branch list may carry side branches of their own, so the whole structure is shaped like a binary tree whose root is the head of the main list.
Flatten the structure into one doubly linked list by splicing every side branch in between its parent node and the node that originally followed the parent. Branches nested inside a branch are spliced in the same way, before the rest of the enclosing branch continues.
The nodes are stored in two arrays. Nodes are labeled `0` to `n - 1`, and node `0` is the head of the main list. `next_node[i]` is the node that follows node `i` in its own list, or `-1` if node `i` is the last node of its list. `branch[i]` is the first node of node `i`'s side branch, or `-1` if node `i` has no side branch.
Implement `flatten_with_branches(next_node, branch)`. Return the flattened doubly linked list as two arrays of length `n`: `result[0][i]` is the node that comes after node `i` in the flattened list (`-1` for the last node), and `result[1][i]` is the node that comes before node `i` (`-1` for node `0`).
### Rules
- In the flattened list, every node is immediately followed by the flattened contents of its side branch, if it has one, and after that by the flattened remainder of the list that originally followed it.
- Node `0` is the first node of the flattened list, and every node appears in it exactly once.
- If no node has a side branch, the flattened list is the main list in its original order, now with backward links. This is the plain singly-to-doubly conversion.
- Side branches do not appear in the output: after flattening, nodes are connected only by their forward and backward links.
- Return exactly two arrays: forward links first, backward links second.
### Example 1
```
Input: next_node = [1, 2, -1], branch = [-1, -1, -1]
Output: [[1, 2, -1], [-1, 0, 1]]
```
There are no side branches. The list `0 -> 1 -> 2` keeps its order and gains backward links.
### Example 2
```
Input: next_node = [1, 2, -1, 4, -1, -1], branch = [-1, 3, -1, 5, -1, -1]
Output: [[1, 3, -1, 5, 2, 4], [-1, 0, 4, 1, 5, 3]]
```
The main list is `0 -> 1 -> 2`. Node `1` has the side branch `3 -> 4`, and node `3` has the side branch `5`. The flattened list is `0 -> 1 -> 3 -> 5 -> 4 -> 2`: node `3`'s branch comes right after node `3`, then the rest of node `1`'s branch (node `4`), then the rest of the main list (node `2`).
### Example 3
```
Input: next_node = [1, -1, 3, -1], branch = [-1, 2, -1, -1]
Output: [[1, 2, 3, -1], [-1, 0, 1, 2]]
```
Node `1` is the last node of the main list and has the side branch `2 -> 3`, so the branch simply extends the list: `0 -> 1 -> 2 -> 3`.
### Constraints
- `1 <= n <= 100000`, where `n = len(next_node) = len(branch)`
- `-1 <= next_node[i] <= n - 1` and `-1 <= branch[i] <= n - 1`
- Node `0` is referenced by no entry of `next_node` or `branch`. Every other node is referenced by exactly one entry across the two arrays, and every node can be reached from node `0` by following `next_node` and `branch` links. The structure therefore has no cycles and no shared nodes.
- Branches may be nested, and the nesting depth can be as large as `n - 1`.
- The output is uniquely determined by the input.
- Every input and output value lies in `[-1, n - 1]`, so it fits in a signed 32-bit integer.
Constraints
- 1 <= n <= 100000, where n = len(next_node) = len(branch)
- -1 <= next_node[i] <= n - 1 and -1 <= branch[i] <= n - 1
- Node 0 is referenced by no entry of next_node or branch. Every other node is referenced by exactly one entry across the two arrays, and every node can be reached from node 0 by following next_node and branch links (no cycles, no shared nodes).
- Branches may be nested, and the nesting depth can be as large as n - 1.
- Every input and output value lies in [-1, n - 1] and fits in a signed 32-bit integer.
Examples
Input: ([1, 2, -1], [-1, -1, -1])
Expected Output: [[1, 2, -1], [-1, 0, 1]]
Input: ([1, 2, -1, 4, -1, -1], [-1, 3, -1, 5, -1, -1])
Expected Output: [[1, 3, -1, 5, 2, 4], [-1, 0, 4, 1, 5, 3]]
Hints
- Treat branch[i] as a left child and next_node[i] as a right child. In what traversal order does the flattened list visit the nodes?
- Once you know the visiting order, the forward and backward links are just consecutive pairs in that order.
- Nesting can be n - 1 levels deep, so a recursive walk can overflow the call stack. Which data structure lets you do the same walk iteratively?