Lowest Common Manager for Employee Groups
Updated
Problem statement
A company reporting hierarchy is a rooted binary tree. The tree is encoded by parallel arrays employeeIds and managerIds. For each index i, managerIds[i] is the direct manager of employeeIds[i]; the root has manager -1.
You also receive a batch of employee groups in queries. For each group, return the employee ID of its lowest common manager: the deepest employee whose subtree contains every employee in that group. An employee is in their own subtree, so a one-employee query returns that employee.
Return one manager ID per query in the original query order. The hierarchy is fixed across the entire batch, so preprocess it to support large or frequent groups efficiently.
Function
lowestCommonManagers(employeeIds: int[], managerIds: int[], queries: int[][]) → int[]Examples
Example 1
employeeIds = [1,2,3,4,5,6,7]managerIds = [-1,1,1,2,2,3,3]queries = [[4,5],[4,6,7],[2,4,5]]return = [2,1,2]Employees 4 and 5 report under 2. The group containing 4, 6, and 7 spans both children of root 1. Employee 2 is itself an ancestor of the final group.
Example 2
employeeIds = [10,20,30,40,50,60]managerIds = [-1,10,10,20,20,40]queries = [[60],[60,50],[30,60]]return = [60,20,10]A singleton group returns 60. Employees 60 and 50 first meet at 20, while 30 and 60 first meet at root 10.
Constraints
1 <= employeeIds.length == managerIds.length <= 100000.- Employee IDs are unique integers from
1through1000000000. - Exactly one entry of
managerIdsis-1; every other entry names an employee inemployeeIds. - The manager relationships form one connected acyclic rooted tree, and each manager has at most two direct reports.
1 <= queries.length <= 100000.- Each query is non-empty, contains unique employee IDs, and every queried ID exists in the hierarchy.
- The total number of employee IDs across all queries is at most
100000.
More Amazon Phone Screen questions
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- 3SumPHONE SCREEN · Seen Nov 2026
- Circular Primes Below a LimitPHONE SCREEN · Seen Nov 2026
- Cheapest Flights Within K StopsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Two SumOA · PHONE SCREEN · Seen Nov 2026
- Count the 1 Bits in a 32-Bit ValuePHONE SCREEN · Seen Nov 2026
Similar questions at other companies
- Lowest Common Manager for Employee GroupsGoogle · PHONE SCREENGoogle interview questions
- Count Distinct Rooted-Tree GraftsThe D.E. Shaw Group · PHONE SCREENThe D.E. Shaw Group interview questions
- File Encryption Tree OptimizationDatabricks · PHONE SCREEN · ONSITE INTERVIEWDatabricks interview questions
- Maximum Path Sum Between Marked NodesDoorDash · PHONE SCREENDoorDash interview questions
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- House Robber IIIOkta · PHONE SCREENOkta interview questions
- House Robber IIIGoldman Sachs · PHONE SCREENGoldman Sachs interview questions
- Account Roles With Parent-User InheritanceStripe · PHONE SCREENStripe interview questions
- House Robber IIIVisa · PHONE SCREENVisa interview questions
- Validate a BST with a Custom ComparisonApple · PHONE SCREENApple interview questions
Amazon interview experiences
- Amazon SWE OA with AI Coding: 1 Experience
- Amazon SWE Intern Phone Screen Interview Experience: 1 Experience
- Amazon New Grad SDE I OA and Virtual Onsite: 1 Experience
- Amazon BIE Intern SQL and Interview Questions: 17 Experiences
- Amazon Experienced SWE AI-Assisted Debugging OA: 1 Experience
- Amazon SDE II (L5) Interview Questions: 5 Experiences