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 easy 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 org chart level by level | Microsoft Coding Question

Traverse org chart level by level

Company: Microsoft

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

## Problem You are given an organization chart as **manager relationships**. Each employee is represented by: - `employee_id` (string/int) - `manager_id` (string/int or `null`), where `null` indicates the CEO/root Assume the org chart forms a valid **tree** (exactly one root, no cycles), but employees may appear in any order. ## Task Return the employees **top-down, level by level** (i.e., breadth-first order). ### Input A list of pairs/records: - `(employee_id, manager_id)` ### Output One of the following (choose one and state which you implement): 1. A list of lists, where each inner list contains employee_ids at the same depth, ordered left-to-right by insertion order (or sorted if you prefer), e.g. `[[CEO], [A,B], [C,D,E]]`; **or** 2. A single list of employee_ids in BFS order. ## Example Input: - ("CEO", null) - ("A", "CEO") - ("B", "CEO") - ("C", "A") Output (option 1): - `[["CEO"], ["A","B"], ["C"]]` ## Constraints / Edge cases - Employees may be given before their manager appears in the input. - Large orgs: aim for `O(n)` time and `O(n)` memory.

Quick Answer: This question evaluates understanding of hierarchical data modeling and tree traversal, specifically breadth-first (level-order) traversal and reconstruction of a tree from manager–employee relationships.

You are given an organization chart as a list of manager relationships. Each relationship is a pair `(employee_id, manager_id)`, where `manager_id` is `None` for the CEO/root. The input may be in any order, so an employee can appear before their manager. The org chart forms a valid tree when the list is non-empty. Return the employees level by level from top to bottom using breadth-first traversal. This problem implements option 1: return a list of lists, where each inner list contains the employee IDs at the same depth. If multiple direct reports share the same manager, keep them in the order their relationships appear in the input. For robustness, if the input list is empty, return `[]`.

Constraints

0 <= n <= 200000, where n is the number of relationships
When n > 0, the relationships form a valid tree with exactly one root and no cycles
Employees may appear before their manager in the input
Aim for O(n) time and O(n) extra space

Examples

Input: ([('CEO', None), ('A', 'CEO'), ('B', 'CEO'), ('C', 'A')],)

Expected Output: [['CEO'], ['A', 'B'], ['C']]

Explanation: CEO is the root. A and B are on level 1, and C is under A on level 2.

Input: ([('C', 'A'), ('CEO', None), ('A', 'CEO'), ('B', 'CEO')],)

Expected Output: [['CEO'], ['A', 'B'], ['C']]

Explanation: C appears before A in the input, but it still belongs under A. The traversal is still level by level from the root.

Input: ([('CEO', None), ('B', 'CEO'), ('A', 'CEO'), ('D', 'A'), ('C', 'A')],)

Expected Output: [['CEO'], ['B', 'A'], ['D', 'C']]

Explanation: Sibling order follows input order: B appears before A under CEO, and D appears before C under A.

Input: ([(4, 2), (2, 1), (1, None), (3, 1), (5, 2)],)

Expected Output: [[1], [2, 3], [4, 5]]

Explanation: The root is 1. Its children are 2 then 3, and 2 has children 4 then 5.

Input: ([(42, None)],)

Expected Output: [[42]]

Explanation: A single employee is both the root and the only level.

Input: ([],)

Expected Output: []

Explanation: With no employees, there are no levels to return.

Hints

First build a mapping from each manager to their direct reports, and remember which employee has `manager_id == None`.
After finding the root, use a queue to process employees breadth-first and collect one level at a time.

Quick Overview

This question evaluates understanding of hierarchical data modeling and tree traversal, specifically breadth-first (level-order) traversal and reconstruction of a tree from manager–employee relationships.