# Build Nested Comments from Parent References You receive a flat collection of comment records. Each record has a unique comment ID, a `parentId` field, and comment data. A root comment has no parent; a reply names another comment as its parent. Design and implement the transformation that produces a nested comment forest in which every comment contains its direct replies. The input records may arrive in any order, so a child can appear before its parent. Explain the data structures, construction steps, validation policy, and complexity. The source format does not specify how malformed references should be treated, so make that policy explicit rather than silently dropping data. ### Constraints & Assumptions - Preserve every comment's existing data while adding a collection of direct children. - Do not require parents to precede children in the input. - Do not assume there is exactly one root. - Define behavior for duplicate IDs, a missing parent, a self-parent, a longer cycle, and a very deep reply chain. - State whether sibling order must follow input order or another supplied ordering field. ### Clarifying Questions to Ask - What value represents “no parent,” and may multiple root comments be returned? - Are comment IDs guaranteed unique, and are all parent IDs expected to exist in the same batch? - Is the desired output mutable objects, copied records, or a serialized structure? - Which field determines sibling order? - Should malformed components reject the entire input, be quarantined, or be returned separately as errors? ```hint Separate identity from attachment Create a way to find the node for any comment ID before trying to connect children to parents. ``` ```hint Validate the resulting graph A parent reference can form a cycle even when every referenced ID exists, so “parent found” is not a complete validity check. ``` ### What a Strong Answer Covers - A two-pass or equivalent linear construction using an ID-to-node index. - Correct handling when a child appears before its parent and when several roots exist. - A deliberate policy for duplicates, missing parents, self-links, cycles, and sibling ordering. - Preservation of input records without accidental shared-state mutation when copying is required. - Cycle detection and an iterative alternative for validation or serialization when nesting may be deep. - Time and space complexity tied to the number of comments and parent links. ### Follow-up Questions 1. How would you update the forest when one new comment arrives at a time? 2. What changes if a parent can arrive much later in a different batch? 3. How would you detect a cycle without recursive stack overflow? 4. How would you support deletion while preserving or reparenting replies? 5. How would you paginate a very large thread without constructing the entire forest in memory?