Find smallest common organization for employees

You are given an organization structure and employee-to-organization membership. Define any reasonable data structures you need.

Part 1 (base)

Assume the org structure is a tree (each org has at most one parent). Each employee belongs to exactly one org node.

Implement a function that returns the smallest / lowest organization that contains both employees (i.e., the lowest common ancestor org of their org nodes).

• Input: employeeAId , employeeBId
• Output: the org id/node representing the minimal common org
• You may assume each org node can have a parent pointer.

Part 2 (follow-up)

Now assume an employee can belong to multiple orgs in the same org tree.

Implement a function that returns the minimal org that contains both employees, meaning:

• the returned org is an ancestor of at least one org of employee A, and
• an ancestor of at least one org of employee B,
• and among all such orgs, it is the “lowest/smallest” one (closest to the employees).

Clarify how you break ties if there are multiple valid minimal orgs.

Part 3 (follow-up)

Now assume an org can belong to multiple parent orgs (i.e., the org structure is a DAG, not a tree). Employees may still belong to one or multiple orgs.

Return the set of minimal common org(s) that satisfy the condition above. (There may be more than one minimal common org in a DAG.)

• Define precisely what “minimal” means in a DAG (e.g., no descendant of that org is also a common org).

Part 4 (follow-up / discussion)

The membership edges (employee→org and org→org) can change over time.

Discuss how you would support:

• add/remove employee membership edges
• add/remove org-to-org edges (while preventing cycles if you require a DAG)
• repeated queries for minimal common org(s)

State what time/space tradeoffs you would target and any constraints/assumptions (e.g., number of orgs, number of employees, query/update ratio).