Find smallest common organization for employees
Company: Atlassian
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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).
Quick Answer: The question evaluates competency in hierarchical and graph data structures, including tree lowest-common-ancestor reasoning, DAG ancestor minimality, membership-set handling, dynamic updates, and algorithmic complexity analysis.
Given org parent edges and employee memberships, return all minimal common ancestor orgs for two employees.
Constraints
- parents maps org -> parent org or list of parent orgs
- memberships maps employee -> list of orgs
Examples
Input: ({'A': ['Root'], 'B': ['Root'], 'C': ['A'], 'D': ['A']}, {'e1': ['C'], 'e2': ['D']}, 'e1', 'e2')
Expected Output: ['A']
Explanation: Tree LCA is A.
Input: ({'A': ['Root'], 'B': ['Root']}, {'e1': ['A', 'B'], 'e2': ['B']}, 'e1', 'e2')
Expected Output: ['B']
Explanation: Multiple membership can produce lower org B.
Input: ({'X': ['A', 'B'], 'A': ['Root'], 'B': ['Root']}, {'e1': ['X'], 'e2': ['A', 'B']}, 'e1', 'e2')
Expected Output: ['A', 'B']
Explanation: DAG can have two minimal common orgs.
Input: ({}, {}, 'missing', 'e2')
Expected Output: []
Explanation: Missing employee has no common org.
Hints
- Compute ancestor sets, intersect them, then remove any common ancestor that has a common descendant.