Katkat
Back

Rebuild a Comment Thread From Flat Records and Draw It

StripeSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Turn unordered reply records into a tree, then print it as an ASCII tree with exact branch connectors, and optionally collapse deep branches. Tests careful spec reading, tree building that doesn't depend on input order, and precise output formatting.

A code-review tool exports discussion comments as a flat list. Your job is to rebuild the threads and print them for a plain-text email digest. Graders compare the output character for character.

Each record is a dict:

{"id": str, "reply_to": str | None, "author": str, "posted_at": int, "body": str}

reply_to is None for a top-level comment. Otherwise it is the id of the comment being answered. Records can arrive in any order.

Part 1: Build the thread structure

Write build_thread(records). It returns the ordered top-level ids, a map from each id to its ordered reply ids, and a lookup from id to record.

  • Order siblings (and top-level comments) by posted_at, breaking ties by id.
  • If a reply points at an id that doesn't exist (its parent was deleted), promote it to top level.
  • Raise ValueError on duplicate ids, and on reply cycles (comments that can never reach a top-level comment).

Part 2: Render

Write render_thread(records) -> str. Each comment's label is "{author}: {body}".

  • Top-level comments are printed flush left.
  • A reply that is not the last among its siblings is prefixed with +-- . The last reply is prefixed with `--.
  • Descendants of a non-last reply carry | in that column. Descendants of a last reply carry four spaces.
  • Join the lines with \n, with no trailing newline.
ravi: Build is red on main
+-- ola: Flaky test again?
|   `-- nova: Same on my side
|       `-- ravi: Filed a ticket
`-- jun: Reverting now
mei: Deploy window moved

Part 3: Collapse deep branches

Add max_depth: int | None = None. Top-level comments are at depth 0. A comment at depth max_depth that has replies shows a single child line, `-- (+N more replies), where N is the size of its entire subtree. Its replies are not printed individually. With max_depth=1, the example becomes:

ravi: Build is red on main
+-- ola: Flaky test again?
|   `-- (+2 more replies)
`-- jun: Reverting now
mei: Deploy window moved

Constraints

  • Up to 10^5 records. Threads can be thousands of levels deep, so avoid recursion depth limits.
  • Rendering should be O(n log n) overall, with sorting as the dominant cost.

Hints

Hint 1

Index every record by id before you link anything. Then the input order doesn't matter.

Hint 2

To detect cycles, walk from the top-level comments and check that you reached every record. Anything you didn't reach is stuck in a cycle.

Hint 3

The prefix for a node's children equals its own prefix plus either '| ' or four spaces, depending on whether the node was the last sibling. Carry that prefix along with each node.

Hint 4

Use an explicit stack and push children in reverse order, so they pop in the right order. That gets you a pre-order traversal without recursion.

Follow-up questions

  • How would you render with Unicode box-drawing characters and still keep the columns aligned?
  • Support the opposite direction: parse a rendered tree back into records.
  • How would you stream the output for a 10 GB export that doesn't fit in memory?
  • Add a filter that prints only threads where a given author participated, keeping the ancestors for context.