Parse Parent-Child Task Records and Render Them as a Connector Tree
Company: Stripe
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Technical Screen
You receive a list of task records and must rebuild the hierarchy of tasks and subtasks they describe, then print it as a text tree. The specification is long and the output format is strict, so reading carefully matters as much as the code. The exercise is split into parts; the first two are below.
There are two kinds of records:
- **Root records** contain the fields `timestamp`, `task`, `task_id` and `task_name`.
- **Child records** contain the fields `timestamp`, `subtask`, `parent_id`, `task_id` and `task_name`. The `parent_id` of a child is the `task_id` of its parent.
### Clarifying Questions
- Is the result returned as one string or printed line by line, and is it compared character for character?
- How many records can there be, and how deep can the nesting go?
### Part 1 — Parse the records into a parent-child map
Parse the records into a structure that maps every task to its child tasks and identifies the root tasks.
```hint Input order
Do not assume that a parent's record appears before the records of its children.
```
#### Clarifying Questions for this Part
- In what form do the records arrive: parsed objects, JSON lines or another text format?
- What do the `task` and `subtask` fields hold, and is a record's kind decided by them or by the presence of `parent_id`?
- Can a child have children of its own?
- What should happen to a record whose `parent_id` matches no task, or to two records that share a `task_id`?
#### What This Part Should Cover
- A map from each parent to its children, plus the list of roots, built independently of input order
- Handling of orphans, duplicate identifiers and cycles in the parent links
- Time and space complexity of the build
### Part 2 — Render the tree with connectors
Print the hierarchy. A root node is printed without any leading connector. A child that is not the last among its siblings is printed after `├─`, and the last child in a sibling group is printed after `└─`. For a root with two children, the output has this shape (the labels are placeholders):
```text
Root task
├─ First child
└─ Last child
```
```hint Two separate decisions
A line's connector depends only on the node's position among its siblings. What goes in front of the connector on deeper lines is a separate decision that depends on the node's ancestors.
```
#### Clarifying Questions for this Part
- What text is printed for each node: the task name, the identifier, or both?
- In what order are siblings and roots printed: by timestamp, by input order or by identifier?
- For grandchildren and deeper nodes, what indentation goes in front of the connector?
#### What This Part Should Cover
- Deterministic sibling ordering and correct detection of the last child
- Correct prefixes at every depth, not only for the direct children of a root
- A traversal that is safe for deep trees, and its cost
### What a Strong Answer Covers
- Confirming the exact output format with the interviewer before coding, given how long the specification is
- A clean separation between parsing and rendering, so each can be tested on its own
- Explicit handling of malformed input instead of silently dropping records
- Output that matches the specification exactly, including the last-child connector
- Enough pace to finish both parts with time left for the next part
### Follow-up Questions
- How would you print only the subtree rooted at a given task?
- If records keep arriving over time, how would you keep the tree up to date and re-render only what changed?
- How would you detect and report a cycle in the parent links?
Overview: A multi-part coding exercise that parses root and child task records, linked by parent identifiers, into a parent-child map and renders the hierarchy as a text tree with branch connectors for middle and last children. It tests careful reading of a long specification, robust tree building and exact output formatting.
Read the full Stripe Software Engineer interview experience this question came from
Community answers
Answer by ff
"""Rebuild a task/subtask hierarchy from flat records and render it as a text tree.
Assumptions (confirm with the interviewer before coding):
Records arrive as dicts, or as JSON strings (one record per string).
A record's kind is decided by the presence of parent_id; the task /
subtask marker is only cross-checked and reported if inconsistent.
Children can have children (arbitrary depth).
Each node prints its task_name.
Roots and siblings are ordered by timestamp, ties broken by input order.
Timestamps must be mutually comparable (all numbers, or all ISO-8601 strings).
Indentation under a non-last ancestor is "│ ", under a last ancestor " ",
so every column lines up with the 3-character connectors "├─ " and "└─ ".
render() returns one string, lines joined by "\n", no trailing newline.
"""
from future import annotations
import json
from dataclasses import dataclass, field
from typing import Any, Iterable
class TaskTreeError(ValueError):
"""Raised in strict mode when the input is malformed."""
@dataclass
class Node:
task_id: Any
name: str
timestamp: Any
seq: int # input position, used as a tie-breaker
parent_id: Any = None # None for root records
@property
def sort_key(self):
return (self.timestamp, self.seq)
@dataclass
class Forest:
nodes: dict[Any, Node]
children: dict[Any, list] # task_id -> ordered child ids
roots: list # ordered root ids
issues: list[str] = field(default_factory=list)
Part 1: parse records into a parent -> children map plus the list of roots
REQUIRED = ("t