Is Students With Invalid Departments easy or hard?

Students With Invalid Departments is classified as an Easy database problem. It mainly tests basic SQL knowledge, specifically joins, subqueries, and filtering rows based on missing matches between tables.

Students With Invalid Departments Python/Java solution

This problem is solved using SQL rather than Python or Java logic. The solution typically uses a MySQL query with either a NOT IN subquery or a LEFT JOIN to identify students whose department_id does not exist in the Departments table.

How to solve Students With Invalid Departments in O(n)?

Use a LEFT JOIN between Students and Departments on department_id and filter rows where the department record is NULL. The database performs a linear scan with join matching, which effectively results in O(n + m) time complexity for the two tables.

What is the best approach for Students With Invalid Departments?

The LEFT JOIN approach is typically the best. Join the Students table with Departments on department_id and filter rows where the department side is NULL. This directly exposes students whose department reference does not exist. It runs in O(n + m) time depending on table sizes.

Is Students With Invalid Departments asked at Google/Amazon/Meta?

SQL join and data integrity problems like this commonly appear in database screening rounds at companies such as Amazon, Meta, and Google. They test your understanding of joins, filtering, and detecting missing relationships between tables.

What data structure is used in Students With Invalid Departments?

The problem uses relational database tables rather than in-memory data structures. SQL engines internally use indexing, hash joins, or nested loop joins to match rows between Students and Departments.

What is the time complexity of Students With Invalid Departments?

Both common solutions run in O(n + m) time, where n is the number of students and m is the number of departments. The database scans the Students table and checks membership using either a join or a subquery result set.

Description Solution Video 5:27

1350. Students With Invalid Departments

Easy89.8% acceptance1 companyPremium elsewhere, free here

Table: Departments

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| id            | int     |
| name          | varchar |
+---------------+---------+
In SQL, id is the primary key of this table.
The table has information about the id of each department of a university.

Table: Students

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| id            | int     |
| name          | varchar |
| department_id | int     |
+---------------+---------+
In SQL, id is the primary key of this table.
The table has information about the id of each student at a university and the id of the department he/she studies at.

Find the id and the name of all students who are enrolled in departments that no longer exist.

Return the result table in any order.

The result format is in the following example.

Example 1:

Input: 
Departments table:
+------+--------------------------+
| id   | name                     |
+------+--------------------------+
| 1    | Electrical Engineering   |
| 7    | Computer Engineering     |
| 13   | Bussiness Administration |
+------+--------------------------+
Students table:
+------+----------+---------------+
| id   | name     | department_id |
+------+----------+---------------+
| 23   | Alice    | 1             |
| 1    | Bob      | 7             |
| 5    | Jennifer | 13            |
| 2    | John     | 14            |
| 4    | Jasmine  | 77            |
| 3    | Steve    | 74            |
| 6    | Luis     | 1             |
| 8    | Jonathan | 7             |
| 7    | Daiana   | 33            |
| 11   | Madelynn | 1             |
+------+----------+---------------+
Output: 
+------+----------+
| id   | name     |
+------+----------+
| 2    | John     |
| 7    | Daiana   |
| 4    | Jasmine  |
| 3    | Steve    |
+------+----------+
Explanation: 
John, Daiana, Steve, and Jasmine are enrolled in departments 14, 33, 74, and 77 respectively. department 14, 33, 74, and 77 do not exist in the Departments table.

Asked at 1 company

Amazon

Topics

Database

5:27

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1

Input

{"headers":{"Departments":["id","name"],"Students":["id","name","department_id"]},"rows":{"Departments":[[1,"Electrical Engineering"],[7,"Computer Engineering"],[13,"Bussiness Administration"]],"Students":[[23,"Alice",1],[1,"Bob",7],[5,"Jennifer",13],[2,"John",14],[4,"Jasmine",77],[3,"Steve",74],[6,"Luis",1],[8,"Jonathan",7],[7,"Daiana",33],[11,"Madelynn",1]]}}

Your code is saved on this device.Solution