Find LCA in organization tree
Company: Atlassian
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
Given an organizational hierarchy tree, return the lowest common organization (parent node) for two or more employees (≥
2). Provide unit tests, detail your tree representation, and discuss how to support dynamic additions and deletions of users/groups with thread-safety considerations.
Overview: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Find LCA in organization tree states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Community answers
Answer by akashchand3071
.
Answer by mdshabaz25a
import java.util.*;
public class Solution {
// Helper class to wrap the result during tree traversal
private static class Result {
int matchCount;
Integer ancestor;
Result(int matchCount, Integer ancestor) {
this.matchCount = matchCount;
this.ancestor = ancestor;
}
}
public static int findNearestCommonManager(List edges, int root, List queries) {
// Step 1: Map the target queries to a Set for O(1) lookups
Set targets = new HashSet<>(queries);
// Step 2: Construct the adjacency tree structure (Manager -> List of Direct Reports)
Map> tree = new HashMap<>();
for (int[] edge : edges) {
int employee = edge[0];
int manager = edge[1];
tree.computeIfAbsent(manager, k -> new ArrayList<>()).add(employee);
}
// Step 3: Run the post-order recursive search from the CEO node
Result finalResult = lcaHelper(root, tree, targets);
return finalResult.ancestor != null ? finalResult.ancestor : root;
}
private static Result lcaHelper(int currentNode, Map> tree, Set targets) {
int totalMatchesFound = 0;
// Check if the current node itself is one of the targeted employees
if (targets.contains(currentNode)) {
totalMatchesFound++;
}
// Recurse through all direct reports (children)
List directReports = tree.getOrDefault(currentNode, Collections.emptyList());
for (int report : directReports) {
Result childResult = lcaHelper(report, tree, targets);
// If an ancestor was already pinpointed down the line, short-circuit and bubble it up
if (childResult.ancestor != null) {
return childResult;
}
totalMatchesF