← Atlassian Interview InsightsSoftware Engineer

Atlassian·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say
Jun 2026Remote

Summary

Atlassian technical phone screen that built on a previous org-tree problem, this time throwing in multi-membership to make things messier. The follow-up nature of it meant I felt like I was playing catch-up the whole time.

Questions Asked (1)

Q1

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, accounting for all memberships. Walk through how the data structure changes, how you'd compute ancestor sets, and how you'd find the deepest common org. What's the time and space complexity?

Algorithms & Data StructuresSystem DesignTechnical Trade-offs
Author's notes

The multi-membership twist genuinely tripped me up at first.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that the problem is a DAG (directed acyclic graph) of organizations with employees as nodes that can belong to multiple orgs. Propose building an ancestor set for each employee by traversing up the org DAG, then intersect the sets to find the deepest common ancestor. Discuss trade-offs between precomputation and on-the-fly computation.

Pro tip: Mention that the org graph is a DAG, not a tree, so you must handle multiple parents and avoid cycles. Also, consider using bitsets for ancestor sets to speed up intersection and depth comparison.

1. Clarify the problem and constraints

Confirm that employees can belong to multiple organizations, and organizations can have multiple parent organizations, forming a DAG. Ask about the size of the org graph, frequency of queries, and whether updates are expected.

2. Model the data structure

Represent the org hierarchy as a directed acyclic graph (DAG) with adjacency lists for parent pointers. For each employee, store a list of direct memberships. Optionally, precompute ancestor sets for each organization or employee.

3. Compute ancestor sets

For each employee, compute the set of all ancestor organizations by traversing up the DAG (e.g., using DFS/BFS with memoization). If precomputing, store these sets in a hash set or bitset per employee.

4. Find deepest common org

Intersect the ancestor sets of the two employees. Among the common ancestors, select the one with maximum depth (longest path from root). If multiple, any deepest works; if none, return null.

5. Analyze complexity and trade-offs

Discuss time and space complexity for both precomputation and query. For on-the-fly: O(V+E) per query. For precomputation: O(N*(V+E)) space and time, but O(min(|A|,|B|)) per query. Mention bitset optimizations.

Key Points to Mention

  • The org structure is a DAG, not a tree, so multiple inheritance and cycles must be handled.
  • Ancestor sets can be computed via DFS/BFS with memoization or topological order.
  • Intersection of ancestor sets yields common ancestors; deepest is the one with maximum depth.
  • Depth can be defined as the longest path from any root to the organization.
  • Precomputing ancestor sets for all employees trades space for faster queries.
  • Bitsets can represent ancestor sets compactly and allow fast intersection via bitwise AND.

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