Org Tree Lowest Common Department

Requirements

• Represent an organization as a hierarchy of departments or groups, with employees either appearing as leaves or recorded as members of a group.
• For a collection of two or more employees, identify the nearest department or group that contains every employee in that collection.
• You may choose the input representation. Possible designs include parent references, explicit tree nodes, or a separate mapping from employees to their groups.
• Create and execute test cases, paying particular attention to input-format decisions and boundary conditions before implementing the solution.
• Consider these extensions:
  • An employee may be assigned to more than one department.
  • A department or organization may have multiple parents, changing the structure from a tree into a DAG.
  • Membership relationships may be inserted, deleted, or otherwise changed while the program is running.
  • Discuss the time and space costs, and determine what structure would best support many repeated queries.

A possible interface, if you choose to expose the operation as a function, is:

Group closestCommonGroup(Organization organization, List<Employee> employees)

Examples

Use an organization with this structure:

Company (group)
├── Eng (group)
│   ├── Platform (group)
│   │   ├── Alice (employee)
│   │   └── Bob (employee)
│   └── Product (group)
│       └── Carol (employee)
└── HR (group)
    └── Dave (employee)

1. input

   employees = [Alice, Bob]

   output

   Platform
   
   Both employees are inside Platform, and no smaller containing group is available.

2. input

   employees = [Alice, Carol]

   output

   Eng
   
   Alice and Carol share Eng, but they belong to different subgroups beneath it.

3. input

   employees = [Alice, Dave]

   output

   Company
   
   Their first common group is the organization root.

Notes

• This is a frequently repeated organization-hierarchy coding prompt across software engineering, intern, and machine-learning interviews.
• The interviewer may want a complete in-memory organization and test fixture rather than a prebuilt coding-platform harness, so allow time to construct the data and run the tests.
• For the multiple-parent version, clarify whether returning any common ancestor is sufficient, whether the lowest common ancestor must be unique, and how ties are represented.

Preparation

• Practice a parent-reference implementation, a depth-first-search approach that builds paths toward the root, and a preprocessing design for handling many queries.
• Include tests for unknown employees, an employee appearing more than once in a query, employees whose groups are in an ancestor/descendant relationship, and ties caused by multiple parents.