← Atlassian Interview InsightsSoftware Engineer

Atlassian·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Atlassian software engineer interview with a tree-based algorithm problem. The question was well-scoped but they pushed on complexity analysis pretty hard afterward.

Questions Asked (1)

Q1

Given a company org chart represented as a tree (departments as internal nodes, employees as leaves), find the deepest department that contains two given employees. Analyze the time and space complexity of your solution.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I went with a recursive approach pretty quickly, basically a lowest common ancestor problem on a tree.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the tree structure and assumptions, then propose an efficient algorithm such as finding the lowest common ancestor (LCA) of the two employees. The deepest department containing both is the LCA if it's an internal node, or its parent if the LCA is an employee. Analyze time and space complexity, typically O(n) time and O(h) space for a recursive DFS approach.

Pro tip: Mention that you would first confirm whether the tree is binary or n-ary, and whether parent pointers are available, as this affects the optimal approach. Also, discuss trade-offs between preprocessing for multiple queries versus a single query.

1. Clarify the problem and assumptions

Ask questions to understand the tree structure (binary vs. n-ary, parent pointers, size), and confirm that the deepest department is the lowest common ancestor that is an internal node.

2. Outline the algorithm

Explain that you will find the LCA of the two employees, then if the LCA is an employee, return its parent; otherwise return the LCA itself.

3. Detail the LCA computation

Describe a recursive DFS that returns the LCA: if the current node is one of the employees, return it; otherwise recurse on children and combine results.

4. Analyze complexity

State that the time complexity is O(n) in the worst case (visiting each node once) and space complexity is O(h) for recursion stack, where h is tree height.

5. Discuss optimizations and trade-offs

Mention that for multiple queries, preprocessing (e.g., binary lifting) can reduce query time to O(log n) at the cost of O(n log n) space.

Key Points to Mention

  • Lowest Common Ancestor (LCA) concept and its relation to the deepest department
  • Handling the case where the LCA is an employee (leaf) and returning its parent
  • Time complexity: O(n) for a single query with DFS, space O(h) for recursion
  • Trade-offs: preprocessing for multiple queries vs. single query efficiency
  • Edge cases: employees not in the same tree, one employee is ancestor of the other
  • Assumptions about tree structure (binary vs. n-ary, parent pointers)

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