Rearrange Guests by Attendance and Absence

Edit PagePage History

TIP102 Unit 3 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 input to the problem?
  • A: The input is a 0-indexed list guests of even length, containing both positive integers (attendees) and negative integers (absences).
• Q: What is the output?
  • A: The output is the guests list rearranged such that every consecutive pair of elements has opposite signs, starting with an attendee, while preserving the relative order of elements with the same sign.
• Q: How should the rearrangement be performed?
  • A: The rearranged list should alternate between attendees and absences, beginning with an attendee, while maintaining the original order within the groups of attendees and absences.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Separate the list into attendees and absences, then alternate between them to construct the final list, ensuring that it starts with an attendee and that the order within each group is preserved.

1. Separate the `guests` list into two lists: one for attendees (positive integers) and one for absences (negative integers).
2. Initialize two pointers, `attendee_index` and `absence_index`, to iterate over the two lists.
3. Initialize an empty list `result` to store the rearranged guests.
4. While both `attendee_index` and `absence_index` are within the bounds of their respective lists:
   1. Append an attendee to `result` from the `attendees` list.
   2. Append an absence to `result` from the `absences` list.
   3. Increment both pointers.
5. Return the `result` list, which now satisfies the conditions.

⚠️ Common Mistakes

• Failing to preserve the relative order of elements within the groups of attendees and absences.
• Not ensuring that the rearranged list starts with an attendee.
• Incorrectly alternating between attendees and absences.

I-mplement

def rearrange_guests(guests):
    # Separate attendees and absences
    attendees = [guest for guest in guests if guest > 0]
    absences = [guest for guest in guests if guest < 0]
    
    # Initialize pointers
    attendee_index = 0
    absence_index = 0
    result = []
    
    # Reconstruct the list alternating between attendees and absences
    while attendee_index < len(attendees) and absence_index < len(absences):
        result.append(attendees[attendee_index])
        result.append(absences[absence_index])
        attendee_index += 1
        absence_index += 1
    
    return result

# Example usage
print(rearrange_guests([3,1,-2,-5,2,-4]))  # Output: [3,-2,1,-5,2,-4]
print(rearrange_guests([-1,1]))            # Output: [1,-1]