Organize the Pirate Crew - codepath/compsci_guides GitHub Wiki

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q
  • What is the desired outcome?
    • To organize the pirates into groups such that each pirate is in a group of size specified by group_sizes[i].
  • What input is provided?
    • An array group_sizes where group_sizes[i] indicates the size of the group pirate i should be in.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Group pirates by their required group size using a dictionary, then form groups by slicing the lists of pirates according to their required size.

1) Initialize a dictionary `size_to_pirates` to map each group size to a list of pirates who need to be in that size group.
2) Iterate through the `group_sizes` array:
   - For each pirate, add their ID to the list in the dictionary corresponding to their required group size.
3) Initialize an empty list `result` to store the final groups.
4) For each group size, take slices of the list of pirates in the dictionary to form groups, and add these groups to the result list.
5) Return the `result` list containing the groups.

⚠️ Common Mistakes

• Forgetting to correctly slice the list of pirates according to the group size.
• Not considering that each pirate must appear in exactly one group.

I-mplement

def organize_pirate_crew(group_sizes):
    # Step 1: Initialize the dictionary
    size_to_pirates = {}
    
    # Step 2: Fill the dictionary with group sizes
    for pirate, size in enumerate(group_sizes):
        if size not in size_to_pirates:
            size_to_pirates[size] = []
        size_to_pirates[size].append(pirate)
    
    # Step 3: Initialize the result list
    result = []
    
    # Step 4: Form groups
    for size, pirates in size_to_pirates.items():
        for i in range(0, len(pirates), size):
            result.append(pirates[i:i + size])
    
    return result