Katkat
Back

Analyze Reports in a Nested Org Chart

PatreonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model hierarchical tree structures and use post-order traversal to aggregate data across deep organizational levels efficiently.

Problem Statement

You are given a list of employees in an organization, represented as a collection of Employee objects. Each object contains an id and a manager_id (which is null if they report to no one). An organization may consist of multiple separate hierarchies (a forest).

Your task is to classify each employee and calculate their impact. Define an employee as a manager if they have at least one direct report, and an individual contributor (IC) otherwise. For each employee, compute:

  1. direct_reports_count: The number of employees who report directly to them.
  2. total_descendants_count: The total number of employees in their entire reporting chain (direct and indirect).

Function Signature

def analyze_org_chart(employees):
    # employees is a list of dictionaries: {'id': int, 'manager_id': int or None}
    # Return a dictionary where key is employee_id and value is:
    # {'is_manager': bool, 'direct': int, 'total': int}

Constraints

  • Number of employees N <= 100,000.
  • Every id is unique.
  • The org chart is guaranteed to be a forest (no cycles).

Example

Input:

[
    {'id': 1, 'manager_id': None}, # CEO
    {'id': 2, 'manager_id': 1},    # Manager
    {'id': 3, 'manager_id': 2},    # IC
    {'id': 4, 'manager_id': 1}     # IC
]

Output:

{
    1: {'is_manager': True, 'direct': 2, 'total': 3},
    2: {'is_manager': True, 'direct': 1, 'total': 1},
    3: {'is_manager': False, 'direct': 0, 'total': 0},
    4: {'is_manager': False, 'direct': 0, 'total': 0}
}

Edge Cases

  • Single employee organization.
  • Deep hierarchies (linked list style) that might trigger recursion depth limits.
  • Disconnected components (forest).

Hints

Hint 1

Build an adjacency list representation where keys are manager IDs and values are lists of direct report IDs to navigate the tree efficiently.

Hint 2

Use a recursive approach or an iterative post-order traversal to calculate total descendants, where an employee's total is the sum of their direct reports' (1 + total descendants) counts.

Hint 3

To avoid stack overflow errors in Python for very deep hierarchies, consider using an iterative approach with a stack or increasing the recursion limit.

Follow-up questions

  • How would your solution change if the organization had a cycle? How would you detect one?
  • If the org chart is updated frequently (employees changing managers), which data structure would allow for the fastest updates to the descendant counts?
  • How would you identify the 'chain of command' path from a specific employee up to the top-level executive?