Arrange Event Attendees by Priority

Edit PagePage History

TIP103 Unit 3 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 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 empty lists:
   * `less` to collect attendees with priority less than the specified priority.
   * `equal` to collect attendees with priority equal to the specified priority.
   * `greater` to collect attendees with priority greater than the specified priority.
2. Iterate through each attendee in `attendees`:
   1. If the current attendee's priority is less than the specified priority:
      * Append it to `less`.
   2. If the current attendee's priority is greater than the specified priority:
      * Append it to `greater`.
   3. If the current attendee's priority is equal to the specified priority:
      * Append it to `equal`.
3. Concatenate `less`, `equal`, and `greater` in order.
4. Return the concatenated result.

⚠️ 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):
    less = []
    equal = []
    greater = []
    
    for attendee in attendees:
        if attendee < priority:
            less.append(attendee)
        elif attendee == priority:
            equal.append(attendee)
        else:
            greater.append(attendee)
    
    return less + equal + greater