Atlassian·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026Remote

Summary

Atlassian technical phone screen that built on a previous org-tree problem, this time with employees belonging to multiple organizations. The twist made it a lot harder than I expected.

Questions Asked (1)

You have the org-tree LCA problem, but now an employee can belong to multiple organizations at once. Given two employees, find the deepest organization that contains both of them. Walk through how you'd change the data structure, compute ancestor sets for each employee, and find the deepest common ancestor. What are the time and space complexity tradeoffs?

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I'd done a version of LCA before so I thought I was fine.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the multi-org membership as a DAG where each employee can have multiple parent organizations, then for each employee compute the set of all ancestor organizations. Find the deepest common organization by intersecting the two ancestor sets and selecting the one with maximum depth (e.g., using topological order or longest path from root).

Pro tip: Clarify upfront whether 'deepest' means maximum distance from any root or maximum number of hops from the employee; also discuss how to handle cycles or multiple roots, as real org structures often have these edge cases.

1. Clarify problem and constraints

Confirm the definition of 'deepest' (e.g., maximum depth from root, or longest path from employee), whether the graph is a DAG or can have cycles, and if there are multiple roots. Ask about expected input size and update frequency.

2. Choose data structure

Represent the org structure as a directed acyclic graph (DAG) with adjacency lists for parent pointers. For each employee, store a list of direct parent organizations. Optionally, precompute depth values for each organization via topological sort.

3. Compute ancestor sets

For each employee, perform a traversal (DFS/BFS) upward to collect all ancestor organizations into a set. Use memoization to avoid recomputing for shared ancestors if multiple queries are expected.

4. Find deepest common ancestor

Intersect the two ancestor sets to get common organizations. Among these, select the one with the maximum depth (precomputed or computed on the fly). If multiple have same depth, any is acceptable unless specified otherwise.

5. Analyze complexity and tradeoffs

Time: O(V+E) per query for traversals plus O(min(|A|,|B|)) for intersection, where V and E are nodes and edges in the DAG. Space: O(V) for ancestor sets. Discuss tradeoffs: precomputing all ancestors for all employees (O(V^2) space) vs. on-the-fly traversal; using bitsets for faster intersection if V is small.

Key Points to Mention

Modeling as a DAG instead of a tree to handle multiple memberships
Using topological sort to compute depths and detect cycles
Ancestor set computation via DFS/BFS with memoization
Set intersection to find common ancestors and selection by max depth
Time complexity: O(V+E) per query, space complexity: O(V) for sets
Tradeoffs between precomputation (faster queries, more space) and on-demand computation (slower queries, less space)

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.