Fabric Pairing

TIP103 Unit 4 Session 1 (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 tuples, where each tuple contains a fabric name (string) and its associated cost (integer).

• Q: What is the output?

  • A: The output is a tuple containing the names of the two fabrics whose combined cost is the closest to the budget without exceeding it.

• Q: What should the function return if no pair of fabrics can be found within the budget?

  • A: The function should return an empty tuple or a predefined value indicating no valid pair was found.

• Q: Are there any constraints on the input, such as the fabrics needing to be sorted?

  • A: The fabrics do not need to be sorted initially; the function will handle sorting.

P-lan

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.

I-mplement

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

6: E-valuate

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

• Time Complexity: O(n log n) where n is the number of fabrics, dominated by the sort step. The two-pointer traversal after sorting is O(n).
• Space Complexity: O(1) because the sort is performed in place and only a constant amount of extra variables are used.