You are given an organization structure and employee-to-organization membership. Define any reasonable data structures you need.
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).
employeeAId
,
employeeBId
parent
pointer.
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:
Clarify how you break ties if there are multiple valid minimal orgs.
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.)
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)
State what time/space tradeoffs you would target and any constraints/assumptions (e.g., number of orgs, number of employees, query/update ratio).