577. Employee Bonus
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 72.0%
Problem Breakdown
Restate the problem in plain language:
We are given two tables, Employee and Bonus. The Employee table contains employee details such as employee_id, name, and salary. The Bonus table contains bonus information for employees, including employee_id and bonus. We need to find the names of all employees who do not have a bonus.
Inputs:
- Two tables:
Employee: with columnsemployee_id,name, andsalary.Bonus: with columnsemployee_idandbonus.
Outputs:
- A list of employee names from the
Employeetable where there is no corresponding entry in theBonustable.
Implicit constraints or tricky edge cases:
- The
Bonustable might be empty. - There could be duplicate entries in either table, but we assume each
employee_idis unique within its respective table. - The
employee_idin both tables should match for a valid bonus entry.
Intuition
Brute-force approach:
- Iterate through each employee in the
Employeetable. - For each employee, check if there is an entry in the
Bonustable with the sameemployee_id. - If no matching entry is found, add the employee’s name to the result list.
This approach would have a time complexity of O(n * m), where n is the number of employees and m is the number of bonus entries. This is inefficient for large datasets.
Key insight:
Instead of checking each employee against all bonuses, we can use SQL joins to efficiently find employees without bonuses. Specifically, we can use a LEFT JOIN between the Employee and Bonus tables on employee_id. Employees without bonuses will have NULL values in the bonus column of the result.
Approach
-
Use a LEFT JOIN:
- Join the
Employeetable with theBonustable onemployee_id. - This will include all employees and their corresponding bonuses, if any.
- Join the
-
Filter out employees without bonuses:
- Use a
WHEREclause to filter rows where the bonus isNULL.
- Use a
-
Select the required columns:
- Select only the
namecolumn from theEmployeetable for the final output.
- Select only the
Complexity Analysis
- Time complexity: O(n + m), where n is the number of employees and m is the number of bonuses. The join operation processes each row in both tables once.
- Space complexity: O(k), where k is the number of employees without bonuses. This is the space required to store the result set.
Solution
# SQL query to find employees without bonuses
SELECT e.name
FROM Employee e
LEFT JOIN Bonus b ON e.employee_id = b.employee_id
WHERE b.bonus IS NULL;
Edge Cases Handled
- Empty
Bonustable: If there are no bonus entries, the join will result in all employees havingNULLin the bonus column, and they will all be selected. - No matching
employee_id: Employees without any bonuses will naturally haveNULLvalues in the bonus column after the join, ensuring they are included in the final result.