Unit 4 Session 1 Advanced (Click for link to problem statements)
Understand what the interviewer is asking for by using test cases and questions about the problem.
Q: What is the structure of the input?
Q: What is the output?
Q: What should the function return if there are fewer than two breaks?
Q: What if there are multiple pairs with the same closest sum?
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.
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