Table: Employee
+-------------+---------+ | Column Name | Type | +-------------+---------+ | id | int | | name | varchar | | department | varchar | | managerId | int | +-------------+---------+ id is the primary key (column with unique values) for this table. Each row of this table indicates the name of an employee, their department, and the id of their manager. If managerId is null, then the employee does not have a manager. No employee will be the manager of themself.
Write a solution to find managers with at least five direct reports.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Employee table: +-----+-------+------------+-----------+ | id | name | department | managerId | +-----+-------+------------+-----------+ | 101 | John | A | null | | 102 | Dan | A | 101 | | 103 | James | A | 101 | | 104 | Amy | A | 101 | | 105 | Anne | A | 101 | | 106 | Ron | B | 101 | +-----+-------+------------+-----------+ Output: +------+ | name | +------+ | John | +------+
The key idea in #570 Managers with at Least 5 Direct Reports is to identify managers who supervise multiple employees in the same table. Since the employee table typically stores a managerId reference, you can treat it as a self-referential relationship where employees point to their managers.
A practical approach is to group employees by their manager identifier and count how many direct reports each manager has. Using SQL aggregation functions like COUNT() along with GROUP BY helps compute the number of reports for each manager. After calculating these counts, you filter managers whose report count meets the required threshold (at least five).
Finally, join the filtered manager identifiers back to the employee table to retrieve the manager names. This approach leverages relational database aggregation and joins, making it efficient for large datasets. The overall complexity mainly depends on the database's grouping operation, which typically scans the table once and performs aggregation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| SQL Aggregation with GROUP BY and HAVING | O(n) | O(n) |
Learn With Chirag
Use these hints if you're stuck. Try solving on your own first.
Try to get all the mangerIDs that have count bigger than 5
Use the last hint's result as a table and do join with origin table at id equals to managerId
This is a very good example to show the performance of SQL code. Try to work out other solutions and you may be surprised by running time difference.
If your solution uses 'IN' function and runs more than 5 seconds, try to optimize it by using 'JOIN' instead.
This approach uses SQL's GROUP BY and HAVING clause to count the number of employees managed by each manager. We group the employees by their managerId and count the occurrences to determine the number of direct reports. We then filter the groups having at least five direct reports and join back with the Employee table to get the names of these managers.
The time complexity of this query depends on the indexing and size of the original table. In general, it's O(n) for counting and filtering operations, where n is the number of rows in the Employee table.
1SELECT e.name FROM Employee e WHERE e.id IN (SELECT managerId FROM Employee WHERE managerId IS NOT NULL GROUP BY managerId HAVING COUNT(id) >= 5);First, we select the managers who have at least five direct reports by counting the number of employees corresponding to each managerId in the subquery. We then use this list to filter the original table and retrieve the names of these managers from the Employee table.
This approach utilizes a join between the table itself, followed by a GROUP BY and filter with a HAVING clause. We join the Employee table with itself on the condition of matching the managerId to id. This join helps to create pairs of managers and their direct reports. By grouping based on the manager's id and applying a HAVING clause, we fetch managers with five or more reports.
The time complexity for this query is similar to the previous approach, influenced by both the number of rows to join and then group. Generally, it would be about O(n) constrained within the database engine optimizations.
1SELECT e1.name FROM Employee e1 JOIN Employee e2 ON e1.id = e2.managerId GROUP This approach involves using a SQL query to group employees by their managerId and then counting how many employees report to each manager. From this, we can filter out managers who have less than five direct reports.
Time Complexity: O(n), where n is the number of employees as we scan the list and group it.
Space Complexity: O(m), where m is the number of unique managerId entries that meet the criteria.
1SELECT e.name
2FROM Employee e
3JOIN (SELECT managerId
4 This solution uses a self join within the table and counts the direct reports for each manager by referring to the managerId.
Time Complexity: O(n), due to the need to scan and join the relationships within the table.
Space Complexity: O(m), where m is the number of distinct managers in the table.
1SELECT e1.name
2FROM Employee e1
3JOIN Employee e2 ON e1.id = e2.managerId
4Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, SQL aggregation and relational queries like this are common in data-focused interviews at FAANG and similar companies. They test your ability to analyze hierarchical relationships and use GROUP BY effectively.
The optimal approach uses SQL aggregation. Group employees by managerId, count the number of direct reports using COUNT(), and filter results with a HAVING clause to keep managers with at least five reports. Then join back to the employee table to get the manager names.
The problem mainly relies on SQL aggregation techniques such as GROUP BY and HAVING. These allow you to group employees by their manager and filter based on the number of direct reports.
This problem uses a self-referencing relationship within a table, where the managerId column references another employee in the same table. Aggregation functions help analyze these relationships efficiently.
In this implementation, we first join the table Employee with itself to create pairs between managers and their direct reports. We then group by the manager's id, counting the number of reports for each manager to filter those with at least five.
We first create a subquery to select managerId from the Employee table, grouping by managerId and including only those managerIds with five or more entries. Then, we join this result with the Employee table to get the names of these managers.
Here, we perform a self join on the Employee table. We join on e1.id and e2.managerId, essentially matching each manager with their subordinates. We then group by the manager's id to count how many subordinates each has, and filter to keep those with at least 5 subordinates.