Employer-Employee Mapping
Filed under Amazon
Free read 3 of 3Confirm if the output requires direct reports only or all descendants in the hierarchy.
The question
Given a list of employer-employee relationships, return a mapping where each employer is mapped to a list of all their direct and indirect reporting employees.
Constraints
- Relationships are given as pairs (employer, employee).
- The organizational structure forms a valid tree or forest.
Examples
- Input
- Relations: [('Alice', 'Bob'), ('Bob', 'Charlie')]
- Output
- {'Alice': ['Bob', 'Charlie'], 'Bob': ['Charlie']}
- Why
- Alice manages Bob directly and Charlie indirectly through Bob.
Approach
Confirm if the output requires direct reports only or all descendants in the hierarchy.
Iterate repeatedly over the relation list until no new indirect reports can be added, which is slow for deep hierarchies.
Build an adjacency list for direct reports, then use DFS with memoization to compute all reports for each manager.
Handle leaf nodes with no reports and empty relation lists.
Solution
O(N^2) time in worst-case deep tree, O(N) space
from collections import defaultdict
def get_all_reports(relations):
direct = defaultdict(list)
for boss, emp in relations:
direct[boss].append(emp)
memo = {}
def dfs(node):
if node in memo:
return memo[node]
reports = []
for child in direct[node]:
reports.append(child)
reports.extend(dfs(child))
memo[node] = reports
return reports
all_managers = set(direct.keys())
return {mgr: dfs(mgr) for mgr in all_managers}
Tips
- What they are testing: Test with flat hierarchies, deep linear chains, and multiple top-level managers.
- Common mistake: Only capturing direct reports instead of aggregating all subordinate nodes recursively.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.