N-ary Index-Path Encoder and Decoder
Bloomberg LP● MediumNEW GRADONSITE INTERVIEWProblem statement
An ordered N-ary tree is represented by parallel arrays. Node 0 is the root. values[i] is * for an internal node or one uppercase English letter for a leaf. children[i] lists node i's children in index order. Every node has at most ten children, every leaf letter is unique, and internal nodes are not operation targets.
A letter's code is the sequence of child indices on the path from the root to that letter. Each index is one digit from 0 through 9. Process operations in order:
["ENCODE", letter]returns that letter's code.["DECODE", code]follows the code from the root and returns the reached letter.
Every operation is valid: encoded letters exist uniquely, and decoded paths end at letter leaves. Return one string for every operation in encounter order.
Function
processNaryCodec(values: String[], children: int[][], operations: String[][]) → String[]Examples
Example 1
values = ["*","*","A","B","C"]children = [[1,4],[2,3],[],[],[]]operations = [["DECODE","01"],["ENCODE","C"],["ENCODE","A"]]return = ["B","1","00"]Path 01 selects root child 0, then its child 1, reaching B. Letter C is root child 1.
Example 2
values = ["*","X","Y","Z"]children = [[1,2,3],[],[],[]]operations = [["ENCODE","Y"],["DECODE","2"],["ENCODE","X"]]return = ["1","Z","0"]All letters are direct root children, so each code is its zero-based child position.
Example 3
values = ["*","*","*","Q"]children = [[1],[2],[3],[]]operations = [["DECODE","000"],["ENCODE","Q"]]return = ["Q","000"]The single-letter leaf is reached through three successive child-zero choices.
Constraints
2 <= values.length <= 100000.children.length == values.length, node0is*, and the arrays form one valid rooted tree.- Every internal node has between
1and10children; every leaf is a unique uppercase English letter. 1 <= operations.length <= 100000.- Every operation is valid, and the total length of all input and output paths is at most
500000.