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 no pair of fabrics can be found within the budget?
Q: Are there any constraints on the input, such as the fabrics needing to be sorted?
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Use a two-pointer technique to find the pair of fabrics whose combined cost is closest to the budget without exceeding it. First, sort the fabrics by their cost, then use two pointers to explore the possible pairs.
1) Sort the `fabrics` list by the cost of each fabric.
2) Initialize two pointers: `left` at the start of the list and `right` at the end.
3) Initialize variables `best_pair` as an empty tuple and `closest_sum` as 0.
4) While `left` is less than `right`:
a) Calculate the sum of the costs of the fabrics at the `left` and `right` pointers.
b) If this sum is closer to the budget than `closest_sum` without exceeding the budget, update `best_pair` and `closest_sum`.
c) If the sum exceeds the budget, move the `right` pointer to the left to reduce the sum.
d) If the sum is within the budget, move the `left` pointer to the right to explore larger sums.
5) Return the `best_pair`.
**⚠️ Common Mistakes**
- Forgetting to handle edge cases where no pair can be found within the budget.
- Mismanaging the pointers, leading to incorrect pairs being selected.
def find_best_fabric_pair(fabrics, budget):
fabrics.sort(key=lambda x: x[1]) # Sort fabrics by cost
left = 0
right = len(fabrics) - 1
best_pair = ()
closest_sum = 0
while left < right:
cost_sum = fabrics[left][1] + fabrics[right][1]
if cost_sum > closest_sum and cost_sum <= budget:
closest_sum = cost_sum
best_pair = (fabrics[left][0], fabrics[right][0])
if cost_sum > budget:
right -= 1
else:
left += 1
return best_pair