Katkat
Back

Traverse org chart level by level

MicrosoftData Scientist · Technical Screen
EasyData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to reconstruct a tree structure from a flat list of relationships and perform a breadth-first search (BFS) to group employees by their organizational depth.

Problem Statement

You are provided with a list of employee-manager relationships. Each employee has a unique ID, and each manager has a unique ID. In this organization, there is only one root node (the CEO), who does not report to anyone (represented by a null manager ID).

Your task is to return the organizational structure level by level. Level 0 should contain the CEO, Level 1 should contain the CEO's direct reports, and so on.

Function Signature

def get_org_levels(relationships):
    # relationships is a list of tuples: (employee_id, manager_id)
    # returns a list of lists, where each inner list contains IDs at that level

Constraints

  • n (number of employees) is between 1 and 10,000.
  • Every employee has at most one manager.
  • There are no circular dependencies.

Examples

Example 1: Input: [(1, None), (2, 1), (3, 1), (4, 2)] Output: [[1], [2, 3], [4]] Explanation: 1 is the CEO. 2 and 3 report to 1. 4 reports to 2.

Example 2: Input: [(10, None), (20, 10), (30, 10), (40, 20), (50, 30)] Output: [[10], [20, 30], [40, 50]]

Edge Cases

  • A single employee (CEO only).
  • A very deep, linear hierarchy (linked list structure).
  • Disconnected components (assume all employees are part of one tree rooted at the CEO).

Hints

Hint 1

Represent the organization as an adjacency list where each manager ID maps to a list of their direct subordinates.

Hint 2

Use a queue to track employees for breadth-first traversal, starting with the CEO who has a manager ID of None.

Hint 3

Process the queue in batches; for each level, iterate through all currently queued employees to gather their subordinates for the next level.

Follow-up questions

  • How would you modify your approach if an employee could have multiple managers (turning the tree into a directed acyclic graph)?
  • What is the time and space complexity of your solution in terms of N employees?
  • If the organizational data were too large to fit in memory, how would you store and query this hierarchy?