Print Org Chart by Level
Company: Microsoft
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an organizational chart as a list of employee records: `(employee_id, manager_id, employee_name)`, where `manager_id` is `null` for the CEO. Assume the organization forms a valid tree with exactly one root and no cycles.
Build the org chart as a tree, then output the employees level by level from top to bottom, showing all employees in the same layer before moving to the next layer.
Explain the data structures you would use, describe the traversal strategy, and analyze the time and space complexity.
Quick Answer: This question evaluates the ability to model hierarchical data, work with tree/graph data structures, select traversal strategies, and analyze time and space complexity when converting flat employee records into a hierarchical org chart.
Build the org tree from employee records and return employee names level by level.
Constraints
- records are (employee_id, manager_id, employee_name).
- Child order follows the input order.
Examples
Input: ([(1,None,"CEO"),(2,1,"Eng"),(3,1,"Sales"),(4,2,"Dev")],)
Expected Output: [['CEO'], ['Eng', 'Sales'], ['Dev']]
Explanation: Level-order traversal from the CEO.
Input: ([],)
Expected Output: []
Explanation: No records produce no levels.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.