Find the Subtasks That Did Not Execute

Find the Subtasks That Did Not Execute

1. What is this problem about?

The Find the Subtasks That Did Not Execute interview question is a data gap analysis task in SQL. You are given two tables: Tasks (listing task IDs and the total number of subtasks each task has) and Executed (listing which specific subtasks for which tasks have actually been completed). Your goal is to generate a report of all subtasks that were not executed for each task.

2. Why is this asked in interviews?

Google asks the Find the Subtasks That Did Not Execute coding problem to test a candidate's ability to generate "missing" data in a relational database. It evaluations your knowledge of Recursive CTEs (Common Table Expressions) or cross joins to build a comprehensive list of all expected subtasks and then compare it with the actual executed subtasks. This is a vital Database interview pattern for reporting and debugging data pipelines.

3. Algorithmic pattern used

This problem follows the Synthetic Sequence Generation pattern.

1. Generate All Subtasks: Since the Tasks table only gives the count of subtasks, you must use a Recursive CTE to generate a row for every subtask index from 1 to subtasks_count for every task.
2. Left Join: Join this full list of expected subtasks with the Executed table on both task_id and subtask_id.
3. Filter: Select only the rows where the Executed table has no match (i.e., where Executed.subtask_id IS NULL).

4. Example explanation

Tasks: (id:1, count:3). Executed: (id:1, sub:1), (id:1, sub:3).

1. Expected List: (1, 1), (1, 2), (1, 3).
2. Join with Executed:
   • (1, 1) matches.
   • (1, 2) matches NULL.
   • (1, 3) matches.
3. Result: (1, 2).

5. Common mistakes candidates make

• Static Join: Trying to join Tasks and Executed directly without generating the subtask sequence first.
• Missing CTE: Forgetting that SQL doesn't have a built-in way to expand a single "count" into multiple rows without recursion or a numbers table.
• Wrong filter: Using an INNER JOIN which would only show subtasks that did execute.

6. Interview preparation tip

Master Recursive CTEs. They are the standard way to expand ranges or build hierarchies in SQL. Understanding how to generate a sequence of numbers on the fly is a common requirement for "Gap Analysis" interview questions.