Atlassian·Software Engineer·Technical Phone Screen·Senior

Senior

Apr 2026

Summary

Atlassian technical phone screen that built on a previous org hierarchy problem, this time extending it to a DAG structure. Solid problem if you've done LCA before, but the multi-parent twist adds enough complexity to trip you up if you're not careful.

Questions Asked (1)

Given an org structure that forms a DAG (each org can have multiple parent orgs), and two employees who each belong to one or more orgs, find the deepest common organization that contains both employees.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This was a follow-up to a tree-based LCA problem, so I had the basic idea ready.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and edge cases, then propose an algorithm that finds all ancestors of each employee and identifies the deepest common ancestor. Discuss trade-offs between different approaches (e.g., BFS vs. DFS, precomputation) and analyze time/space complexity.

Pro tip: Mention that the 'deepest' common org should be measured by distance from the employees (or from the roots), and consider if multiple deepest common orgs exist. Also, discuss how to handle cycles or if the graph is not a DAG.

1. Clarify Requirements and Assumptions

Ask about the input format, whether the DAG is given as an adjacency list, and if employees can belong to multiple orgs. Confirm that 'deepest' means maximum distance from the employees or from the roots.

2. Outline a Brute-Force Approach

For each employee, traverse upwards to find all ancestor orgs. Then find the intersection of the two sets and select the one with maximum depth.

3. Optimize with Bidirectional Search or Precomputation

If multiple queries are expected, precompute ancestor sets or depths for all orgs. Alternatively, use bidirectional BFS from both employees to find the deepest common ancestor efficiently.

4. Analyze Complexity and Trade-offs

Compare time and space complexity of different approaches. Discuss when to use BFS vs. DFS, and how precomputation affects query time.

5. Handle Edge Cases and Extensions

Consider cases where employees share no common org, multiple deepest common orgs exist, or the graph has cycles. Discuss how to extend to weighted edges or dynamic updates.

Key Points to Mention

Graph traversal algorithms (BFS/DFS) for finding ancestors
Set intersection to find common ancestors
Depth calculation and comparison to find the deepest common org
Time and space complexity analysis (e.g., O(N+E) for traversal)
Trade-offs between precomputation and on-the-fly computation for multiple queries
Handling edge cases: no common ancestor, multiple deepest common orgs, cycles

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