Reveal Attendee List in Order - codepath/compsci_guides GitHub Wiki

Unit 3 Session 2 (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 goal of this problem?
  • A: The goal is to reorder the list of registration numbers so that when the numbers are revealed in the specified process, they appear in increasing order.
• Q: What kind of input will be provided?
  • A: A list of unique registration numbers (integers).
• Q: What is the output?
  • A: A reordered list of registration numbers.
• Q: Can the input list contain duplicate numbers?
  • A: No, the numbers are unique.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

**General Idea:** 
We need to simulate the process of revealing the registration numbers while ensuring that the numbers appear in increasing order when revealed. To achieve this:
1. Sort the `attendees` list in increasing order.
2. Use a queue to track the positions where numbers should be placed.
3. Place the smallest number in the first position, then simulate the rotation process by moving the next position to the end of the queue.
4. Repeat this process until all numbers are placed in the correct order.

**Pseudocode:**

1. Sort the list of attendees.
2. Create a queue that holds the indices (positions) of the list.
3. Loop over the sorted attendee list:
   - Take the smallest number and assign it to the position indicated by the front of the queue.
   - Remove that position from the queue.
   - If there are still positions left in the queue:
     - Move the front position to the back of the queue.
4. Return the list with the attendees in the correct order.

⚠️ Common Mistakes

• Forgetting to handle the rotation process of moving the index to the back of the queue.
• Not sorting the attendees list correctly before starting the placement process.

I-mplement

from collections import deque

def reveal_attendee_list_in_order(attendees):
    n = len(attendees)
    index_queue = deque(range(n))
    result = [0] * n

    for attendee in sorted(attendees):
        result[index_queue.popleft()] = attendee
        if index_queue:
            index_queue.append(index_queue.popleft())

    return result