Quick 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.

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

  1. A character is produced only at the moment a leaf is reached. Where must decoding continue from right after that?
  2. 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].
  3. The encoding is guaranteed valid, so you never finish partway down a path, and an empty codes list has nothing to decode.

Decode a Message with an N-ary Prefix-Code Tree

mediumBloombergSoftware Engineer

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)

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

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

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).

Examples

Example 1
Input
([[1, 2, 3], [4, 5], [], [6, 7], [], [], [], [8, 9], [], []], ['', '', 'c', '', 'a', 'b', 'd', '', 'e', 'f'], [0, 1, 1, 2, 1, 0])
Output
'bce'
Notes
Source example 1: codewords of lengths 2, 1 and 3 decode to b, c and e.
Example 2
Input
([[1, 2, 3], [4, 5], [], [6, 7], [], [], [], [8, 9], [], []], ['', '', 'c', '', 'a', 'b', 'd', '', 'e', 'f'], [2, 0, 0, 0, 2, 1, 1])
Output
'daf'
Notes
Source example 2: decoding restarts at the root after each of the leaves d, a and 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.

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def decode_message(children: list[list[int]], chars: list[str], codes: list[int]) -> str:
Sample call
decode_message([[1, 2, 3], [4, 5], [], [6, 7], [], [], [], [8, 9], [], []], ['', '', 'c', '', 'a', 'b', 'd', '', 'e', 'f'], [0, 1, 1, 2, 1, 0])
Language
Case 1
Input
([[1, 2, 3], [4, 5], [], [6, 7], [], [], [], [8, 9], [], []], ['', '', 'c', '', 'a', 'b', 'd', '', 'e', 'f'], [0, 1, 1, 2, 1, 0])
Expected
'bce'
Case 2
Input
([[1, 2, 3], [4, 5], [], [6, 7], [], [], [], [8, 9], [], []], ['', '', 'c', '', 'a', 'b', 'd', '', 'e', 'f'], [2, 0, 0, 0, 2, 1, 1])
Expected
'daf'

Browse More Questions

Show the approach

Approach

Walk the tree one code at a time with a single cursor node, starting at the root 0. For each code c, move to children[node][c]. If that node has no children it is a leaf: append chars[node] to the output and reset the cursor to the root.

Invariant: before each code is read, the cursor is the node reached from the root by the codes read since the last emitted character (the root itself at the start and right after every leaf).

Correctness: characters live only at leaves, so the code is prefix-free and the moment the walk reaches a leaf is exactly the end of one codeword. The emitted character is therefore the unique decoding of that segment, and resetting to the root makes the next codeword start where the rules require. The valid-encoding guarantee means every index is in range and the last code lands on a leaf, so nothing is left over and no partial path needs handling.

Edge cases: an empty codes returns the empty string without touching the tree; a root with a single child still resets to node 0, not to that child; node ids need not follow BFS or DFS order, so every step looks the child up in children instead of computing an id; a long chain of single-child nodes is handled iteratively, so depth never matters; repeated leaf characters need no special care because only the reached leaf matters.

The output pieces are collected in a list (StringBuilder in Java, std::string in C++) and joined once, so each code costs O(1).

Time complexity:
O(n), where n = len(codes)
Space complexity:
O(n) for the output string