Format a Forest of Nested Comments
Company: Amazon
Role: Frontend Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
A backend returns comments in arbitrary parent-before-child order. Each comment has an ID, an optional parent ID, and text. Format every root and descendant as a deterministic tree while preserving the input order among siblings.
## Function Contract
Implement `format_comments(comments)` and return a list of formatted lines. Each comment is `[id, parent_id, text]`; a root uses the empty string as its parent ID.
## Rules
- Root lines are formatted as `id + " " + text` with no tree prefix.
- A non-final child uses `├─ ` and the final child uses `└─ `.
- For deeper descendants, each ancestor contributes `│ ` when more siblings follow at that ancestor, otherwise three spaces.
- Every parent appears before its children in the input, IDs are unique, and every non-empty parent ID exists.
- Return roots in input order and traverse each tree in preorder.
## Constraints
- `0 <= len(comments) <= 200000`.
- IDs and text do not contain newline characters.
- The total text length is at most `2,000,000`.
## Examples
```text
comments = [
["c1", "", "Root"],
["c2", "c1", "First reply"],
["c3", "c1", "Last reply"],
["c4", "c2", "Nested"]
]
output = [
"c1 Root",
"├─ c2 First reply",
"│ └─ c4 Nested",
"└─ c3 Last reply"
]
```
Overview: Format an arbitrarily ordered forest of comments as deterministic preorder trees while preserving sibling order and drawing correct continuation and final-child connectors at every depth.
Read the full Amazon Frontend Engineer interview experience this question came from
Each comment is [id, parent_id, text], with the empty string identifying a root. Parents appear before their children, but records from different trees may be interleaved. Return every tree as formatted lines in preorder, preserving input order among roots and among siblings. A root is id + one space + text with no prefix. Use ├─ plus a space for a non-final child and └─ plus a space for a final child. At deeper levels, each ancestor contributes │ followed by two spaces when more siblings follow there, otherwise three spaces.
Constraints
- 0 <= len(comments) <= 200000.
- Each comment is [id, parent_id, text]; roots use an empty parent ID.
- IDs are unique, every nonempty parent ID identifies an earlier record, and IDs and text contain no newlines.
- The total text length is at most 2000000.
Examples
Input: ([['c1', '', 'Root'], ['c2', 'c1', 'First reply'], ['c3', 'c1', 'Last reply'], ['c4', 'c2', 'Nested']],)
Expected Output: ['c1 Root', '├─ c2 First reply', '│ └─ c4 Nested', '└─ c3 Last reply']
Explanation: The example uses a continuing root branch for c2's nested reply.
Input: ([],)
Expected Output: []
Explanation: No comments produce no formatted lines.
Hints
- Appending children as records arrive preserves sibling input order.
- Carry whether each ancestor has later siblings when constructing a descendant's prefix.