Traverse an Org Chart by Level
Company: Microsoft
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an organization's reporting structure as a flat list of employee-manager relationships. Exactly one employee is the root (the CEO) and has no manager.
Example input schema:
- `employee_id: int`
- `employee_name: string`
- `manager_id: int | null`
Task:
1. Convert the flat reporting structure into a tree.
2. Return the org chart from top to bottom, one level at a time.
3. Each level should be shown in full before moving to the next level.
Example output format:
- `[[CEO], [VP1, VP2], [Mgr1, Mgr2, Mgr3], ...]`
Discuss:
- your data structures,
- time and space complexity,
- and how you would handle invalid input such as cycles, missing managers, or multiple roots.
Quick Answer: This question evaluates understanding of tree and graph data structures, transforming flat employee-manager relations into a hierarchical org chart, level-order traversal, and reasoning about data integrity issues such as cycles, missing managers, or multiple roots.