Optimizing Break Times - codepath/compsci_guides GitHub Wiki

Unit 4 Session 1 Advanced (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 structure of the input?

  • A: The input is a list of integers representing the duration of each break in minutes and a target time in minutes.

• Q: What is the output?

  • A: The output is a tuple containing two integers that represent the pair of break durations whose sum is closest to the target time.

• Q: What should the function return if there are fewer than two breaks?

  • A: The function should return an empty tuple.

• Q: What if there are multiple pairs with the same closest sum?

  • A: The function should return the pair with the smallest break durations.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Sort the break times and use a two-pointer technique to find the pair of durations that sum closest to the target time. Track the pair with the smallest difference from the target, updating when a closer or smaller pair is found.

1) If `break_times` has fewer than 2 elements, return an empty tuple.
2) Sort the `break_times` list in ascending order.
3) Initialize two pointers: `left_pointer` at the start of the list and `right_pointer` at the end.
4) Initialize variables `closest_sum` to infinity and `best_pair` to an empty tuple.
5) While `left_pointer` is less than `right_pointer`:
   a) Calculate `current_sum` as the sum of the values at `left_pointer` and `right_pointer`.
   b) If `current_sum` is closer to `target` than `closest_sum`, update `closest_sum` and `best_pair`.
   c) If `current_sum` equals `closest_sum` but the new pair has smaller values, update `best_pair`.
   d) If `current_sum` is less than `target`, increment `left_pointer`.
   e) If `current_sum` is greater than or equal to `target`, decrement `right_pointer`.
6) Return `best_pair`.

**⚠️ Common Mistakes**

- Forgetting to check if there are fewer than two elements in `break_times`.
- Not handling ties correctly when multiple pairs have the same closest sum.

I-mplement

def find_best_break_pair(break_times, target):
    if len(break_times) < 2:
        return ()

    break_times.sort()
    left_pointer = 0
    right_pointer = len(break_times) - 1
    closest_sum = float('inf')
    best_pair = ()

    while left_pointer < right_pointer:
        current_sum = break_times[left_pointer] + break_times[right_pointer]

        if abs(target - current_sum) < abs(target - closest_sum):
            closest_sum = current_sum
            best_pair = (break_times[left_pointer], break_times[right_pointer])
        elif abs(target - current_sum) == abs(target - closest_sum):
            # Update if the new pair has smaller values, or if the current sum is closer
            if not best_pair or (break_times[left_pointer] < best_pair[0] or break_times[right_pointer] < best_pair[1]):
                best_pair = (break_times[left_pointer], break_times[right_pointer])

        if current_sum < target:
            left_pointer += 1
        else:
            right_pointer -= 1

    return best_pair