Org Chart from a Reporting List: Count Orgs, Print by Level, Find a Common Manager

A company's employees are given as a list of tuples `(id, title, reports_to)`, where `reports_to` is the `id` of the employee's direct manager. The head of an org has `reports_to = None`. Solve the three levels below on the same data. None of them is hard, but all three are expected within about 25 minutes, so correct, quick and clean code matters as much as the idea. This example is used throughout: ```python employees = [ (4, "Engineer", 2), (1, "CEO", None), (8, "Designer", 7), (2, "VP Engineering", 1), (6, "Account Executive", 3), (3, "VP Sales", 1), (5, "Engineer", 2), (7, "Founder", None), ] ``` ### Constraints and Clarifications - IDs are unique. Titles are informational and can repeat. - The list is in no particular order: an employee can appear before their manager. - Unless you choose to validate the input, assume every non-null `reports_to` is the ID of an employee in the list and that there are no reporting cycles. ### Clarifying Questions - Is an org exactly one reporting tree under a head whose `reports_to` is `None`? - What should happen if a `reports_to` value points to an ID that is not in the list? - Should the code detect duplicate IDs or reporting cycles, or can the input be trusted? ### Part 1 — Count the orgs Return the number of orgs in the company, where an org is a head (an employee whose `reports_to` is `None`) together with everyone who reports to that head directly or indirectly. For the example, the answer is `2`. ```hint One pass or a traversal? Ask whether counting needs to walk the trees at all when the input is valid, and what would change if it were not. ``` #### What This Part Should Cover - A count consistent with the stated definition of an org, including for an empty list - Linear time, with no assumption that heads appear first in the list - What the count becomes when a manager ID is missing or the data contains a cycle ### Part 2 — Print employees level by level Print the employees level by level: the heads on the first line, everyone who reports directly to a head on the second line, their direct reports on the third line, and so on. For the example, one acceptable output is: ```text 1 (CEO), 7 (Founder) 2 (VP Engineering), 3 (VP Sales), 8 (Designer) 4 (Engineer), 5 (Engineer), 6 (Account Executive) ``` ```hint Reverse the pointers Each record points up to a manager, but printing walks down. Build what you need for walking down once, before the traversal starts. ``` ```hint Where a level ends Decide how your traversal knows that one level is finished and the next one begins. ``` #### Clarifying Questions for this Part - Within a line, what order is expected: grouped by manager, by ID, or by input order? - Should each org be printed separately, or should employees at the same depth in different orgs share a line, as in the example output? #### What This Part Should Cover - Turning the manager pointers into a list of direct reports per manager - A traversal that visits levels in order and separates them - A deterministic order within each line, and an explicit choice for more than one org - Linear time and space ### Part 3 — First common manager Given the IDs of two employees, return their first common manager: the lowest employee in the hierarchy whom both report to, directly or indirectly. In the example, employees `4` and `5` share manager `2`; the reporting chains of employees `4` and `6` first meet at `1`; employees `4` and `8` are in different orgs and have no common manager. ```hint Two paths upward Each employee has exactly one path up to the head of their org. Think about what two such paths look like once they meet. ``` ```hint Uneven depths If you want to avoid extra memory, consider what to do first when the two employees sit at different depths. ``` #### Clarifying Questions for this Part - If one employee manages the other, directly or indirectly, is the answer that employee, or that employee's own manager? - What should be returned when the two employees are in different orgs, or when an ID does not exist? - Is this asked once, or many times on the same data? #### What This Part Should Cover - Walking manager chains upward through an ID-to-manager map - A correct meeting rule, including when one employee is above the other and when both IDs are the same - The no-answer cases: different orgs and unknown IDs - Time and memory per query in terms of the depth of the hierarchy ### What a Strong Answer Covers - One index of the data, by ID and by manager, built once and reused by all three levels - Correct results in every level when the company has more than one org - Explicit behavior for bad input: unknown managers, duplicate IDs and cycles - Complexity for each level: linear for the first two, proportional to depth per query for the third - Working code for all three levels within the time box, checked against the example and small edge cases ### Follow-up Questions - Level 3 is now called many thousands of times on the same chart. What would you precompute so that each query is fast? - How would you detect a reporting cycle in the input, and report the employees on it? - Extend Level 1 to return the size and the depth of each org. - How would you find the first common manager of a group of more than two employees?