Report Chain

Problem Overview

You are given an org chart as a list[list[str]]. Each inner list has the form: [manager, report_1, report_2, ...]. For example:

python [ ["A", "B", "C"], ["B", "E"], ["C", "D"], ... ]

Problem Statement

Write a function to generate a report chain for a given employee in the organization. The report chain is a list of names starting from the given employee and going up the chain of command to the top of the organization.

Constraints

• The input list represents the org chart.
• Each inner list has the form [manager, report_1, report_2, ...].
• The employee to find the report chain for is given as a string.

Examples

1. Given the org chart:

python [ ["A", "B", "C"], ["B", "E"], ["C", "D"], ["E"], ["D"] ]

And the employee "D", the function should return ["D", "C", "A"].

2. Given the org chart:

python [ ["A", "B", "C", "D"], ["B", "E"], ["C", "F"], ["D"], ["E"], ["F"] ]

And the employee "E", the function should return ["E", "B", "A"].

Hints

• You may need to create a mapping from each employee to their manager.
• Use a breadth-first search (BFS) or depth-first search (DFS) to traverse up the chain of command.

Solution

`python def build_graph(org_chart): graph = {} for entry in org_chart: manager = entry[0] for report in entry[1:]: if report not in graph: graph[report] = [] graph[report].append(manager) return graph

def find_report_chain(org_chart, employee): graph = build_graph(org_chart) chain = [] while employee in graph: chain.append(employee) employee = graph[employee][0] chain.append(employee) return chain[::-1]

Example usage:

org_chart = [ ["A", "B", "C"], ["B", "E"], ["C", "D"], ["E"], ["D"] ]

employee = "D" print(find_report_chain(org_chart, employee)) # Output: ["D", "C", "A"] `

This solution first builds a graph where each node points to its manager. Then, it traverses up the chain of command starting from the given employee until it reaches the top of the organization. The chain is collected in reverse order and then reversed to produce the correct order.