Katkat
Back

Format a Forest of Nested Comments

AmazonFrontend Engineer · Onsite
MediumFrontend EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to reconstruct hierarchical relationships from flat input data and format them into a visual tree representation with specific character-based connectors.

Problem Statement

You are given a list of Comment objects, where each object contains an id, a parentId (null if it is a root comment), and a text string. The comments are provided in an arbitrary order.

Your task is to return a single string representing the comments formatted as a nested tree. Each node should be preceded by a prefix of pipe symbols (|) and spaces to indicate depth, ending with a connector (|-- for non-final children or +-- for the final child of a parent).

Constraints

  • id and parentId are integers.
  • The root comments are those with parentId set to null.
  • Siblings must be displayed in the order they appeared in the original list.

Example

Input:

comments = [
    {"id": 1, "parentId": None, "text": "Root A"},
    {"id": 2, "parentId": 1, "text": "Child A1"},
    {"id": 3, "parentId": 1, "text": "Child A2"},
    {"id": 4, "parentId": 2, "text": "Grandchild A1-1"}
]

Output:

Root A
|-- Child A1
|   |-- Grandchild A1-1
|-- Child A2

Function Signature

def format_comments(comments: list[dict]) -> str:
    pass

Hints

Hint 1

First, convert the flat list into an adjacency list representation where each comment maps to a list of its direct children.

Hint 2

Perform a Depth-First Search (DFS) or recursive traversal starting from the root nodes, maintaining a string prefix that tracks the current depth's visual connectors.

Hint 3

When traversing, keep track of whether the current node is the 'last child' of its parent to determine whether to use '|-- ' or '+-- ' and whether to append a '|' or a space to the prefix for subsequent levels.

Follow-up questions

  • How would you optimize this if the comment forest contained millions of nodes?
  • How would you handle a situation where the input data contains cycles (e.g., A is a parent of B, B is a parent of A)?
  • What changes would be required if we needed to sort children alphabetically by their 'text' property rather than keeping their original input order?