Decode a Message With an N-ary Prefix Code Tree of Child Indices
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A Huffman-style prefix code is stored as an N-ary tree: every character sits in a leaf, and the code for a character is the sequence of child indices on the path from the root to its leaf. Given the tree and an encoded sequence of child indices, decode the message. Start at the root and follow the child named by each index in turn; when you reach a leaf, output its character and go back to the root for the next index. Return the decoded string.
### Function Signature
```python
def decode_message(children: list[list[int]], chars: list[str], codes: list[int]) -> str:
```
### Rules
- Nodes are numbered `0` to `m - 1`, where `m = len(children) = len(chars)`, and node `0` is the root.
- `children[v]` lists node `v`'s children in order, so code `c` applied at node `v` moves to node `children[v][c]`. Child indices start at 0.
- A node is a leaf exactly when `children[v]` is empty, and then `chars[v]` is its one-character string. For an internal node, `chars[v]` is `""`.
- Decoding starts at the root. On reaching a leaf, append its character to the output and return to the root before reading the next code.
- `codes` is a valid encoding: every code is a valid child index for the node it is applied at, and the last code, if any, lands on a leaf, so no partial path is left over.
- An empty `codes` decodes to the empty string.
### Constraints
- `2 <= m <= 10^4`
- The nodes form one tree rooted at node `0`: every node other than the root appears in exactly one `children` list, and the root is an internal node.
- `1 <= len(children[v]) <= 100` for every internal node `v`.
- `0 <= len(codes) <= 10^5` and `0 <= codes[i] <= 99`.
- Every leaf character is a printable ASCII character; a space is allowed.
### Examples
All three examples use this tree; each node is shown as `id` or `id:char`.
```text
0
/ | \
1 2:c 3
/ \ / \
4:a 5:b 6:d 7
/ \
8:e 9:f
```
```text
children = [[1, 2, 3], [4, 5], [], [6, 7], [], [], [], [8, 9], [], []]
chars = ["", "", "c", "", "a", "b", "d", "", "e", "f"]
```
**Example 1**
```text
Input: codes = [0, 1, 1, 2, 1, 0]
Output: "bce"
```
Codes `0, 1` lead from the root to node 1 and then node 5 (`b`). Code `1` leads to node 2 (`c`). Codes `2, 1, 0` lead to node 3, node 7 and node 8 (`e`).
**Example 2**
```text
Input: codes = [2, 0, 0, 0, 2, 1, 1]
Output: "daf"
```
Codes `2, 0` reach node 6 (`d`), codes `0, 0` reach node 4 (`a`), and codes `2, 1, 1` reach node 9 (`f`).
**Example 3**
```text
Input: codes = []
Output: ""
```
Overview: A tree traversal coding question: decode a sequence of child indices using an N-ary, Huffman-style prefix code tree whose leaves hold characters, returning to the root after each leaf. It tests careful walking over a flat tree representation and building the decoded string efficiently.
A Huffman-style prefix code is stored as an N-ary tree: every character sits in a leaf, and the code for a character is the sequence of child indices on the path from the root to its leaf. Given the tree and an encoded sequence of child indices, decode the message.
Implement `decode_message(children, chars, codes)` and return the decoded string.
**Rules**
- Nodes are numbered `0` to `m - 1`, where `m = len(children) = len(chars)`, and node `0` is the root.
- `children[v]` lists node `v`'s children in order, so code `c` applied at node `v` moves to node `children[v][c]`. Child indices start at 0.
- A node is a leaf exactly when `children[v]` is empty, and then `chars[v]` is its one-character string. For an internal node, `chars[v]` is `""`.
- Decoding starts at the root. Follow the child named by each code in turn; on reaching a leaf, append its character to the output and return to the root before reading the next code.
- `codes` is a valid encoding: every code is a valid child index for the node it is applied at, and the last code, if any, lands on a leaf, so no partial path is left over.
- An empty `codes` decodes to the empty string.
The output holds one character per leaf reached, so it is at most `len(codes)` characters long. Every number in the input fits in a 32-bit signed integer.
**Constraints**
- `2 <= m <= 10^4`
- The nodes form one tree rooted at node `0`: every node other than the root appears in exactly one `children` list, and the root is an internal node.
- `1 <= len(children[v]) <= 100` for every internal node `v`.
- `0 <= len(codes) <= 10^5` and `0 <= codes[i] <= 99`.
- Every leaf character is a printable ASCII character; a space is allowed. Two leaves may hold the same character.
**Example tree** (used by both examples)
```text
children = [[1, 2, 3], [4, 5], [], [6, 7], [], [], [], [8, 9], [], []]
chars = ["", "", "c", "", "a", "b", "d", "", "e", "f"]
```
The root `0` has children `1`, `2` (`c`) and `3`. Node `1` has the leaves `4` (`a`) and `5` (`b`). Node `3` has the leaf `6` (`d`) and the internal node `7`, whose leaves are `8` (`e`) and `9` (`f`).
**Example 1**
```text
Input: codes = [0, 1, 1, 2, 1, 0]
Output: "bce"
```
Codes `0, 1` lead from the root to node 1 and then node 5 (`b`). Code `1` leads to node 2 (`c`). Codes `2, 1, 0` lead to node 3, node 7 and node 8 (`e`).
**Example 2**
```text
Input: codes = [2, 0, 0, 0, 2, 1, 1]
Output: "daf"
```
Codes `2, 0` reach node 6 (`d`), codes `0, 0` reach node 4 (`a`), and codes `2, 1, 1` reach node 9 (`f`).
Constraints
- 2 <= m <= 10^4, where m = len(children) = len(chars)
- The nodes form one tree rooted at node 0: every node other than the root appears in exactly one children list, and the root is an internal node.
- 1 <= len(children[v]) <= 100 for every internal node v; children[v] is empty exactly when v is a leaf.
- 0 <= len(codes) <= 10^5 and 0 <= codes[i] <= 99
- Every leaf character is a single printable ASCII character (a space is allowed; two leaves may hold the same character); chars[v] is "" for every internal node v.
- codes is a valid encoding: each code is a valid child index at the node where it is applied, and the last code, if any, lands on a leaf.
Examples
Input: ([[1, 2, 3], [4, 5], [], [6, 7], [], [], [], [8, 9], [], []], ['', '', 'c', '', 'a', 'b', 'd', '', 'e', 'f'], [0, 1, 1, 2, 1, 0])
Expected Output: 'bce'
Explanation: Source example 1: codewords of lengths 2, 1 and 3 decode to b, c and e.
Input: ([[1, 2, 3], [4, 5], [], [6, 7], [], [], [], [8, 9], [], []], ['', '', 'c', '', 'a', 'b', 'd', '', 'e', 'f'], [2, 0, 0, 0, 2, 1, 1])
Expected Output: 'daf'
Explanation: Source example 2: decoding restarts at the root after each of the leaves d, a and f.
Hints
- A character is produced only at the moment a leaf is reached. Where must decoding continue from right after that?
- A node is a leaf exactly when its children list is empty, and node ids carry no positional meaning, so always find a child through children[v].
- The encoding is guaranteed valid, so you never finish partway down a path, and an empty codes list has nothing to decode.