Render an Organization Chart and Find Skip-Level Pairs
Company: Snapchat
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Build an organization tree from manager/direct-report rows. Support rendering the tree with indentation and listing all skip-level pairs, where the second employee is exactly two edges below the first.
Implement `org_chart(relations: string[][], mode: int) -> string[]`:
- A row `[manager, child1, child2, ...]` lists that manager's direct reports in display order.
- `mode == 0`: return the rendered lines in preorder. Prefix each employee with four dots per depth level; the root has no prefix.
- `mode == 1`: return skip-level pairs encoded as `manager,employee`, with one comma and no spaces. Visit managers in tree preorder; for each manager, visit its children and then each child's children in the stored order.
### Constraints & Assumptions
- Each employee name is a nonempty ASCII string of letters, digits, or underscores.
- Each manager appears as the first item of at most one row, and no direct-report list contains a duplicate.
- The rows describe one valid rooted tree with at most 2,000 employees: no cycles, one parent per non-root employee, and exactly one root. The root is not separately supplied.
- A one-element row can represent an employee with no reports. An empty relation list represents an empty chart and returns an empty list in either mode.
- Employees that appear only as children are leaves. Preserve input child order; do not alphabetize it.
- The mode interface and pair serialization are explicit practice encodings of the reported class methods. Skip-level means exactly two levels, not all descendants beyond one level.
### Examples
```text
relations = [["A","B","C"],["B","E"],["C","D"]]
mode = 0
result = ["A","....B","........E","....C","........D"]
```
```text
relations = [["A","B","C"],["B","E"],["C","D"]]
mode = 1
result = ["A,E","A,D"]
```
Explain the time and space costs of building the tree, rendering it, and listing skip-level pairs, including the size of the returned strings. Describe tests for a single root, a chain, and a branching tree.
```hint Separate depth from skip-level distance
Rendering uses each node's depth from the root. A skip-level pair uses only a manager's children and their children, regardless of that manager's absolute depth.
```
Overview: Build and render an organization tree with ordered indentation, infer its root, and return exactly two-level manager-descendant pairs.
Read the full Snapchat Machine Learning Engineer interview experience this question came from
Build an organization tree from manager/direct-report rows. Support rendering the tree with indentation and listing all skip-level pairs, where the second employee is exactly two edges below the first.
Implement `org_chart(relations: string[][], mode: int) -> string[]`:
- A row `[manager, child1, child2, ...]` lists that manager's direct reports in display order.
- `mode == 0`: return the rendered lines in preorder. Prefix each employee with four dots per depth level; the root has no prefix.
- `mode == 1`: return skip-level pairs encoded as `manager,employee`, with one comma and no spaces. Visit managers in tree preorder; for each manager, visit its children and then each child's children in the stored order.
### Constraints & Assumptions
- Each employee name is a nonempty ASCII string of letters, digits, or underscores.
- Each manager appears as the first item of at most one row, and no direct-report list contains a duplicate.
- The rows describe one valid rooted tree with at most 2,000 employees: no cycles, one parent per non-root employee, and exactly one root. The root is not separately supplied.
- A one-element row can represent an employee with no reports. An empty relation list represents an empty chart and returns an empty list in either mode.
- Employees that appear only as children are leaves. Preserve input child order; do not alphabetize it.
- The mode interface and pair serialization are explicit practice encodings of the reported class methods. Skip-level means exactly two levels, not all descendants beyond one level.
### Examples
```text
relations = [["A","B","C"],["B","E"],["C","D"]]
mode = 0
result = ["A","....B","........E","....C","........D"]
```
```text
relations = [["A","B","C"],["B","E"],["C","D"]]
mode = 1
result = ["A,E","A,D"]
```
Explain the time and space costs of building the tree, rendering it, and listing skip-level pairs, including the size of the returned strings. Describe tests for a single root, a chain, and a branching tree.
```hint Separate depth from skip-level distance
Rendering uses each node's depth from the root. A skip-level pair uses only a manager's children and their children, regardless of that manager's absolute depth.
```
Constraints
- Relations is empty or defines one valid rooted tree with at most 2000 employees; names are nonempty ASCII letters/digits/underscores.
- Each manager appears first in at most one row, and each direct-report list is ordered without duplicates.
- Nonroot nodes have exactly one parent, no cycles exist, and the root is the unique name with no parent.
- Child-only employees are leaves; one-element rows are valid. Mode is 0 or 1.
- Mode 0 renders preorder with four dots per depth. Mode 1 visits managers in preorder and emits exactly two-edge pairs as manager,employee in stored child/grandchild order.
- Empty charts return [] in both modes; do not alphabetize names.
Examples
Input: ([['A', 'B', 'C'], ['B', 'E'], ['C', 'D']], 0)
Expected Output: ['A', '....B', '........E', '....C', '........D']
Explanation: Rendering uses preorder with four dots per depth.
Input: ([['A', 'B', 'C'], ['B', 'E'], ['C', 'D']], 1)
Expected Output: ['A,E', 'A,D']
Explanation: Skip-level pairs follow stored child and grandchild order.