Problem Breakdown
The problem requires identifying all employees who have a specific reportsTo value matching a given manager_id.
Inputs:
- A list of dictionaries representing the
Employeetable (employeeId,name,reportsTo). - An integer or identifier for the target
manager_id.
Outputs:
- A sorted list (by
employeeId) containing only those employees where their direct supervisor is the given manager.
Implicit Constraints & Edge Cases:
- NULL Handling: The
reportsTocolumn can be NULL (None in Python). This must not match a valid integer ID unless explicitly handled, though typically we filter for equality with an existing ID. - Empty Input: If the employee list is empty or no matches exist, return an empty list without errors.
- Deterministic Order: SQL queries require consistent ordering; sorting by
employeeIdensures this requirement is met in Python logic.
Intuition
The task maps directly to a database query: SELECT * FROM Employee WHERE reportsTo = manager_id AND reportsTo IS NOT NULL.
Key Insight:
We do not need recursion or self-joins because the relationship is direct (one-to-many from Manager to Employees). The solution reduces to iterating through the dataset once, checking for equality on a specific column. Sorting at the end ensures compliance with SQL ordering requirements (ORDER BY employeeId).
Approach
- Initialize: Create an empty list
resultsto store matching employees. - Iterate & Filter: Loop through each record in the input dataset. Check if
reportsTois not None and equalsmanager_id. - Collect Data: If conditions are met, append a dictionary containing only required fields (
employeeId,name) toresults. - Sort: Sort the collected results by
employeeIdin ascending order. - Return: Output the final sorted list of dictionaries.
Complexity Analysis
- Time Complexity: O(N + M log K), where N is the number of employees, and K (M) is the count of matching reports found during iteration. The initial scan takes O(N). Sorting the result set takes O(K log K). In typical scenarios where matches are a subset or proportional to N, this simplifies effectively to linear time for filtering plus logarithmic overhead for sorting results.
- Space Complexity: O(M), where M is the number of matching employees stored in the output list. We do not store intermediate data structures beyond the input and result set.
Solution
def find_direct_reports(employees: list[dict], manager_id) -> list[dict]:
"""
Identifies all employees who report directly to a specific manager ID.
Args:
employees (list): List of dicts with keys 'employeeId', 'name', 'reportsTo'.
manager_id (int/None): The target manager's employee ID.
Returns:
list[dict]: Filtered and sorted list of matching employees by employeeId.
"""
# Initialize result container for direct reports
results = []
# Iterate through each employee record in the dataset
for emp in employees:
# Check if 'reportsTo' is not None AND matches target manager_id
# Using .get() handles potential missing keys gracefully, defaulting to None.
# This prevents matching against a non-existent ID or NULLs correctly.
reports_to = emp.get('reportsTo')
# Ensure we only match if the reported-to value is valid and equals target
if reports_to is not None and reports_to == manager_id:
results.append({
"employeeId": emp["employeeId"],
"name": emp["name"]
})
# Sort by employeeId to ensure deterministic ordering (standard SQL behavior)
results.sort(key=lambda x: x["employeeId"])
return results
# Example usage context for clarity in interview walkthroughs
if __name__ == "__main__":
sample_data = [
{"employeeId": 1, "name": "John", "reportsTo": None},
{"employeeId": 2, "name": "Jane", "reportsTo": 3},
{"employeeId": 3, "name": "Bob", "reportsTo": 4}
]
# Query for manager with ID 3 (Bob). Jane reports TO Bob.
target_manager = 3
direct_reports = find_direct_reports(sample_data, target_manager)
print(direct_reports)
# Expected Output: [{'employeeId': 2, 'name': 'Jane'}]
Edge Cases Handled
- NULL
reportsTo: The code explicitly checksemp.get('reportsTo') is not None. This prevents matching employees who have no manager against a valid integer ID. - Empty Input List: If the input list is empty, the loop does not execute, and an empty list is returned immediately without error.
- No Matches Found: The
resultslist remains empty if no one reports to the given ID; this returns a clean empty result set rather than raising exceptions or returning partial data. - Missing Keys: Using
.get('reportsTo')safely handles cases where an employee record might be malformed and lack the manager column, preventing key errors during iteration by defaulting to None (which fails equality check against integer ID).