Katkat
Back

Print Org Chart by Level

MicrosoftData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model a tree structure from flat parent-child relations and perform a level-order traversal to format hierarchical data.

Problem Statement

You are given a list of employee records, where each record contains an employee's ID, their name, and their manager's ID. Your goal is to print the organizational chart level by level, starting from the CEO (the employee with no manager).

If multiple employees exist at the same level, print them in the order they appear in the input list. The root (CEO) is considered Level 0.

Input

A list of dictionaries, where each dict has keys: id (int), name (str), and manager_id (int or None).

Output

Return a list of lists, where each inner list contains the names of employees at that specific depth level.

Example

employees = [
    {"id": 1, "name": "Alice", "manager_id": None},
    {"id": 2, "name": "Bob", "manager_id": 1},
    {"id": 3, "name": "Charlie", "manager_id": 1},
    {"id": 4, "name": "David", "manager_id": 2}
]
# Output: [["Alice"], ["Bob", "Charlie"], ["David"]]

Constraints

  • The number of employees is at most 10,000.
  • IDs are unique.
  • The org structure is guaranteed to be a valid tree (no cycles).

Edge Cases

  • Empty input list: return an empty list.
  • Disconnected components: assume only one tree root exists.
  • Single-node tree: return [["Name"]].

Hints

Hint 1

First, convert the flat list into an adjacency list representation where each manager ID maps to a list of direct reports.

Hint 2

Use a queue to perform a Breadth-First Search (BFS) starting from the root node to process nodes level by level.

Hint 3

Keep track of the current queue size at the beginning of each iteration to process exactly one 'level' at a time.

Follow-up questions

  • How would your approach change if the company had multiple CEOs (forming a forest rather than a single tree)?
  • What is the time and space complexity of your solution, and can you optimize the space if the tree is extremely deep (skewed)?
  • How would you handle a scenario where an employee can have two managers (turning the tree into a Directed Acyclic Graph)?