Schedule Banquet Tasks - codepath/compsci_guides GitHub Wiki

Unit 11 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 45 mins
• 🛠️ Topics: Topological Sort, Graph Algorithms

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• What does each dependency mean?
  • prerequisites[i] = [task_a, task_b] means that task_b must be completed before task_a.
• How should the tasks be ordered?
  • The tasks should be ordered such that all prerequisites are satisfied before starting any dependent task.
• What if there are circular dependencies?
  • If circular dependencies exist, return an empty array.

HAPPY CASE
Input: tasks = [""set_table"", ""prepare_dessert""], prerequisites = [""prepare_dessert"", ""set_table""](/codepath/compsci_guides/wiki/""prepare_dessert"",-""set_table"")
Output: [""set_table"", ""prepare_dessert""]
Explanation: You need to set the table before you can prepare dessert.

EDGE CASE
Input: tasks = [""only_task""], prerequisites = []
Output: [""only_task""]
Explanation: There's only one task, so no ordering is required.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Task Scheduling with Dependencies, we want to consider the following approaches:

• Topological Sort: When tasks have dependencies, topological sort ensures that tasks are completed in the correct order.
• Graph Traversal: Treat tasks as nodes and prerequisites as directed edges between them.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use topological sort (BFS) to determine the order of tasks. Start with tasks that have no dependencies (in-degree 0) and remove dependencies as tasks are completed.

1) Initialize a graph (adjacency list) and an in-degree map to track dependencies.
2) For each prerequisite, update the graph and increment the in-degree of the dependent task.
3) Use a queue to keep track of tasks with no dependencies (in-degree 0).
4) While the queue is not empty:
    a) Remove a task from the queue, add it to the result.
    b) Reduce the in-degree of its dependent tasks.
    c) If a task's in-degree becomes 0, add it to the queue.
5) If the result contains all tasks, return the result. Otherwise, return an empty array (circular dependency detected).

⚠️ Common Mistakes

• Forgetting to update in-degrees after processing a task.
• Not handling cycles in the task dependencies properly.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

# Function to determine task order for banquet preparation
def prepare_banquet(tasks, prerequisites):
    # Step 1: Initialize graph and in-degree map
    graph = {task: [] for task in tasks}
    in_degree = {task: 0 for task in tasks}
    
    # Step 2: Build the graph and update in-degrees
    for task_a, task_b in prerequisites:
        graph[task_b].append(task_a)  # task_b must be done before task_a
        in_degree[task_a] += 1
    
    # Step 3: Find all tasks with in-degree 0 (no dependencies)
    queue = deque([task for task in tasks if in_degree[task] == 0])
    
    # Step 4: Perform topological sort
    order = []
    while queue:
        current_task = queue.popleft()
        order.append(current_task)
        
        # Decrease the in-degree of all dependent tasks
        for neighbor in graph[current_task]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Step 5: If the result contains all tasks, return the order. Otherwise, return an empty list.
    if len(order) == len(tasks):
        return order
    else:
        return []

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

• Input: tasks = [""set_table"", ""prepare_dessert""], prerequisites = ""prepare_dessert"", ""set_table""
• Expected Output: [""set_table"", ""prepare_dessert""]
• Watchlist:
  • Ensure the topological sort correctly handles task dependencies.
  • Verify that tasks with no prerequisites are processed first.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume V is the number of tasks and E is the number of dependencies.

• Time Complexity: O(V + E) because we process each task and dependency once.
• Space Complexity: O(V + E) due to the graph representation and in-degree tracking.