How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Microsoft.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Microsoft during technical interviews.

Traverse an Org Chart by Level | Microsoft Coding Question

Quick Overview

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.

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.

You are given an organization's reporting structure as a flat list of employee records. Each record has the form [employee_id, employee_name, manager_id], where manager_id is None for the CEO. Convert the flat reporting structure into an org chart tree and return the employee names from top to bottom, one level at a time. Each level must be completed before moving to the next level. Children under the same manager should appear in the same relative order as they appear in the input list. If the input is invalid, return an empty list. Invalid input includes: no employees, duplicate employee IDs, multiple roots, no root, a missing manager reference, or a cycle/disconnected component.

Constraints

0 <= len(employees) <= 100000
employee_id values must be unique for valid input
Exactly one employee must have manager_id == None for valid input
Every non-root manager_id must refer to an existing employee_id
The reporting structure must form one connected acyclic tree
Employee names may repeat

Examples

Input: ([[1, 'Mira CEO', None], [2, 'Nora VP', 1], [3, 'Omar VP', 1], [4, 'Priya Mgr', 2], [5, 'Quinn Mgr', 2], [6, 'Ravi Mgr', 3], [7, 'Sara IC', 4]],)

Expected Output: [['Mira CEO'], ['Nora VP', 'Omar VP'], ['Priya Mgr', 'Quinn Mgr', 'Ravi Mgr'], ['Sara IC']]

Explanation: The CEO is first, then both VPs, then all managers under those VPs, then the individual contributor under Priya.

Input: ([[2, 'VP Eng', 1], [4, 'Eng Mgr', 2], [1, 'CEO', None], [3, 'VP Sales', 1]],)

Expected Output: [['CEO'], ['VP Eng', 'VP Sales'], ['Eng Mgr']]

Explanation: The root does not need to appear first in the input. Children of CEO appear in their input order: VP Eng before VP Sales.

Hints

Build a mapping from manager_id to the list of direct reports. This gives you the tree edges.
After finding the root, use BFS with a queue to collect employees level by level. Track visited IDs to detect cycles or unreachable employees.