Arrange Event Attendees by Priority - codepath/compsci_guides GitHub Wiki

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 list attendees where each element represents the priority level of an attendee, and an integer priority that indicates a particular level of priority.
• Q: What is the output?
  • A: The output is the attendees list rearranged such that attendees with lower priority appear first, followed by those with the exact priority, and finally those with higher priority, while preserving the relative order within each group.
• Q: How should attendees be arranged with respect to the given priority?
  • A: Attendees with a priority less than the specified priority should be placed first, followed by attendees with the exact priority, and then those with a higher priority.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a three-way partitioning approach similar to the Dutch National Flag problem to rearrange the attendees list according to the specified priority while maintaining the relative order within each group.

1. Initialize three pointers:
   * `left` to track the end of the less-than-priority group.
   * `right` to track the start of the greater-than-priority group.
   * `i` to iterate through the list.
2. Iterate through the `attendees` list using `i`:
   1. If the current attendee's priority is less than the specified priority:
      * Swap it with the element at `left`.
      * Increment both `left` and `i`.
   2. If the current attendee's priority is greater than the specified priority:
      * Swap it with the element at `right`.
      * Decrement `right`.
   3. If the current attendee's priority is equal to the specified priority:
      * Just increment `i`.
3. Continue this process until `i` passes `right`.
4. Return the modified `attendees` list.

⚠️ Common Mistakes

• Incorrectly swapping elements, which could disrupt the relative order within priority groups.
• Failing to handle edge cases where all elements are less than, equal to, or greater than the specified priority.
• Mismanaging the pointers, leading to an infinite loop or incorrect partitioning.

I-mplement

def arrange_attendees_by_priority(attendees, priority):
    n = len(attendees) - 1
    left = 0
    right = n
    i = 0
    
    while i <= right:
        if attendees[i] < priority:
            attendees[left], attendees[i] = attendees[i], attendees[left]
            left += 1
            i += 1
        elif attendees[i] > priority:
            attendees[right], attendees[i] = attendees[i], attendees[right]
            right -= 1
        else:
            i += 1
            
    j = n
    right+=1
    
    while right < n:
         attendees[j], attendees[right] = attendees[right], attendees[j]
         right+=1
        
    
    return attendees