Planning Your Daily Work Schedule - codepath/compsci_guides GitHub Wiki

Unit 4 Session 2 Standard (Click for link to problem statements)

U-nderstand

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

• Q: What is the goal of the problem?
  • A: The goal is to determine if there exists a pair of tasks from a given list whose combined time exactly matches a specified available time slot.
• Q: What should the function return?
  • A: The function should return True if such a pair exists, and False otherwise.
• Q: What are the inputs?
  • A: The inputs are a list of integers (task_times) representing the time required for each task and an integer (available_time) representing the available time slot.
• Q: What are the outputs?
  • A: The output is a boolean (True or False).
• Q: Are there any constraints?
  • A: The list of task times can contain positive integers, and the available time slot is also a positive integer.
• Q: Can there be multiple pairs that satisfy the condition?
  • A: Yes, but the function only needs to determine if at least one pair exists.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a set to track the times that have been seen so far. For each task time in the list, calculate its complement, which is the difference between the available time and the current task time. If the complement exists in the set, then a pair has been found.

1) Initialize an empty set called `task_set`.
2) Iterate through each `time` in the `task_times` list.
   a) Calculate `complement` as `available_time - time`.
   b) If `complement` is in `task_set`, return `True`.
   c) Otherwise, add `time` to `task_set`.
3) If no such pair is found after the loop, return `False`.

**⚠️ Common Mistakes**

- Forgetting to check if the complement is in the set before adding the current task time.
- Assuming the task list is sorted when it may not be.
- Not considering edge cases where the list is empty or has only one task.

I-mplement

def find_task_pair(task_times, available_time):
    task_set = set()

    for time in task_times:
        complement = available_time - time
        if complement in task_set:
            return True
        task_set.add(time)

    return False

Example Usage:

task_times = [30, 45, 60, 90, 120]
available_time = 105
print(find_task_pair(task_times, available_time))  # Output: True

task_times_2 = [15, 25, 35, 45, 55]
available_time = 100
print(find_task_pair(task_times_2, available_time))  # Output: True

task_times_3 = [20, 30, 50, 70]
available_time = 60
print(find_task_pair(task_times_3, available_time))  # Output: False