1350. Students With Invalid Departments
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 1
Acceptance rate: 90.4%
Problem Breakdown
The problem “Students With Invalid Departments” involves identifying students who are enrolled in departments that no longer exist. Given two tables: students and departments, we need to find the list of student names who are associated with departments that do not have a corresponding entry in the departments table.
-
Inputs:
students: A table with columnsstudent_id(primary key) andname.departments: A table with columnsdepartment_id(primary key).
-
Outputs:
- A list of student names who are enrolled in invalid departments.
-
Implicit Constraints/Edge Cases:
- The
studentstable may contain students with duplicate department IDs, but each student ID is unique. - The
departmentstable may be empty, meaning all students are in invalid departments. - There might be no students at all (empty
studentstable).
- The
Intuition
A brute-force approach would involve iterating over each student and checking if their department exists in the departments table. This would require a nested loop, resulting in a time complexity of O(n * m), where n is the number of students and m is the number of departments.
The key insight to improve this solution is to use SQL’s set operations or joins to efficiently find students with invalid departments without needing nested loops. Specifically, we can use a LEFT JOIN to identify students whose department IDs do not match any in the departments table.
Approach
- Identify Invalid Departments: Use a subquery to select all
department_ids from thestudentstable that are not present in thedepartmentstable. - Filter Students: Perform a
LEFT JOINbetween thestudentsanddepartmentstables ondepartment_id. Filter the results to include only those students whose department is invalid (i.e., where the join condition fails). - Select Student Names: Extract the names of these students.
Algorithm Steps:
- Write a subquery to find all
department_ids instudentsthat are not indepartments. - Use this subquery to filter students with invalid departments.
- Select and return the names of these students.
Complexity Analysis
-
Time Complexity: O(n + m), where n is the number of rows in the
studentstable and m is the number of rows in thedepartmentstable. The join operation and subquery are linear with respect to the size of each table. -
Space Complexity: O(k), where k is the number of students with invalid departments. This space is used for storing the result set.
Solution
# SQL query to find students with invalid departments
SELECT s.name
FROM students s
LEFT JOIN departments d ON s.department_id = d.department_id
WHERE d.department_id IS NULL;
Edge Cases Handled
-
Empty
departmentsTable: If thedepartmentstable is empty, all students will have an invalid department, and the query will return all student names. -
Empty
studentsTable: If there are no students, the query will naturally return an empty result set. -
Duplicate Department IDs in
students: The query handles duplicates by filtering based on the absence of a matching department ID, ensuring each student is only listed once if their department is invalid.