Render a Comment Hierarchy
Amazon● MediumNEW GRADONSITE INTERVIEWProblem statement
You are given three parallel arrays describing a flat collection of comments:
ids[i]is the unique ID of commenti.parentIds[i]is-1when commentiis a root; otherwise it is the ID of that comment's parent.texts[i]is the comment text.
The parent relationships form a valid acyclic forest and may have arbitrary depth. A parent may appear before or after its children in the input.
Render the forest in preorder. Preserve input order among root comments and among comments that share the same parent. Return one output string per comment. A comment at depth d is rendered as exactly 2 * d spaces followed by its text.
Function
renderCommentHierarchy(ids: int[], parentIds: int[], texts: String[]) → String[]Examples
Example 1
ids = [10,20,30,40,50]parentIds = [-1,10,10,20,-1]texts = ["Root A","Reply A1","Reply A2","Deep reply","Root B"]return = ["Root A"," Reply A1"," Deep reply"," Reply A2","Root B"]The first root is followed by its children in input order. The child of Reply A1 has depth two, so it receives four leading spaces. The second root is rendered last.
Example 2
ids = [4,2,1,3]parentIds = [2,1,-1,1]texts = ["deep","first child","root","second child"]return = ["root"," first child"," deep"," second child"]The root appears after two descendants in the flat input, but parent IDs still reconstruct the tree. Among the root's children, comment 2 precedes comment 3 because it appeared earlier in the input.
Example 3
ids = [5,6,7]parentIds = [-1,-1,6]texts = ["alpha","beta","gamma"]return = ["alpha","beta"," gamma"]The two roots keep their input order. Comment 7 is the only child of the second root.
Constraints
0 <= ids.length = parentIds.length = texts.length <= 100000.- Every value in
idsis unique and is not-1. - Every
parentIds[i]is either-1or a value present inids. - The parent relationships contain no cycle.
- Every value in
textsis a non-null string.