How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview 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 Interview Question

Q: Traverse org chart level by level

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.

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):

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
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.

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):

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

A single list of employee_ids in BFS order.

Traverse org chart level by level

Quick Overview

Problem

Task

Input

Output

Example

Constraints / Edge cases

Comments (0)

Traverse org chart level by level

Quick Overview

Problem

Task

Input

Output

Example

Constraints / Edge cases

Comments (0)