Queue of Performance Requests - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 Session 2 Standard (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 of tuples requests, where each tuple consists of a priority number and a performance name.
  • Q: What is the output?
    • A: The output is a list of performance names in the order they should be processed, with higher priority performances processed before lower priority ones.
  • Q: How should the performances be processed?
    • A: Performances should be processed in the order of their priorities, with the highest priority being processed first. If two performances have the same priority, they should be processed in the order they appear in the input list.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Sort the requests by priority in descending order and then process them in that order using a queue.

1. Sort the `requests` list in descending order based on the priority (first element of each tuple).
2. Initialize a queue and load the sorted requests into it.
3. Initialize an empty list `result` to store the order of performances.
4. Dequeue each request from the queue and append the performance name to the `result` list.
5. Return the `result` list.

⚠️ Common Mistakes

  • Forgetting to sort the requests by priority before processing them.
  • Incorrectly processing performances with the same priority out of order.
  • Mismanaging the queue, leading to incorrect order of processing.

I-mplement

from collections import deque

def process_performance_requests(requests):
    # Step 1: Sort the requests by priority in descending order
    queue = deque(sorted(requests, reverse=True))
    
    # Step 2: Initialize the result list
    result = []
    
    # Step 3: Process each request in order of priority
    while queue:
        priority, performance = queue.popleft()
        result.append(performance)
    
    # Step 4: Return the final order of performances
    return result

# Example usage
print(process_performance_requests([(3, 'Dance'), (5, 'Music'), (1, 'Drama')]))
# Output: ['Music', 'Dance', 'Drama']

print(process_performance_requests([(2, 'Poetry'), (1, 'Magic Show'), (4, 'Concert'), (3, 'Stand-up Comedy')]))
# Output: ['Concert', 'Stand-up Comedy', 'Poetry', 'Magic Show']

print(process_performance_requests([(1, 'Art Exhibition'), (3, 'Film Screening'), (2, 'Workshop'), (5, 'Keynote Speech'), (4, 'Panel Discussion')]))
# Output: ['Keynote Speech', 'Panel Discussion', 'Film Screening', 'Workshop', 'Art Exhibition']