Fabric Roll Organizer - 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, where each integer represents the length of a fabric roll.

• Q: What is the output?

  • A: The output is a list of tuples, where each tuple contains two fabric roll lengths with the minimum difference between them. If there's an odd number of rolls, the last roll should be returned separately.

• Q: How should the fabric rolls be organized?

  • A: The fabric rolls should be paired such that the difference between the lengths of the rolls in each pair is minimized.

• Q: What should the function return if there is an odd number of fabric rolls?

  • A: The function should return the last unpaired roll as a separate item in the list.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Sort the fabric rolls by their length, then pair them sequentially to minimize the difference in lengths. If there's an odd number of rolls, the last roll remains unpaired.

1) Sort the `fabric_rolls` list in ascending order.
2) Initialize an empty list called `pairs`.
3) While the length of `fabric_rolls` is greater than 1:
   a) Pop the smallest element (first in the sorted list) and the next smallest element.
   b) Append these two elements as a tuple to the `pairs` list.
4) If there is one fabric roll left unpaired, append it to the `pairs` list as a single element.
5) Return the `pairs` list.

**⚠️ Common Mistakes**

- Forgetting to handle the case where there is an odd number of rolls, leaving one unpaired.
- Not correctly sorting the rolls, which can lead to suboptimal pairing.

I-mplement

def organize_fabric_rolls(fabric_rolls):
    fabric_rolls.sort()  # Sort the fabric rolls by length
    pairs = []

    while len(fabric_rolls) > 1:
        smallest = fabric_rolls.pop(0)
        closest = fabric_rolls.pop(0)
        pairs.append((smallest, closest))

    if fabric_rolls:
        return pairs + [fabric_rolls[0]]
    else:
        return pairs