Manage Performance Stage Changes

Edit PagePage History

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 changes of strings where each string represents a change action on the performance schedule.
• Q: What is the output?
  • A: The output is a list of performance IDs that remain scheduled on the stage after all changes have been applied.
• Q: What actions can be performed?
  • A: The actions include "Schedule X", which schedules a performance, "Cancel", which cancels the most recent unscheduled performance, and "Reschedule", which reschedules the most recently canceled performance.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use two stacks to manage the scheduled and canceled performances. The main stack (stack) tracks scheduled performances, while the canceled stack keeps track of canceled performances that might be rescheduled.

1. Initialize an empty stack `stack` to keep track of scheduled performances.
2. Initialize an empty stack `canceled` to keep track of canceled performances.
3. Iterate through each change action in the `changes` list:
   1. If the action starts with `"Schedule"`, extract the performance ID and push it onto `stack`.
   2. If the action is `"Cancel"` and `stack` is not empty, pop the top performance from `stack` and push it onto `canceled`.
   3. If the action is `"Reschedule"` and `canceled` is not empty, pop the top performance from `canceled` and push it back onto `stack`.
4. After processing all changes, return the contents of `stack` as the list of scheduled performances.

⚠️ Common Mistakes

• Forgetting to handle the case where "Cancel" or "Reschedule" is called when there are no performances to cancel or reschedule.
• Not correctly managing the relationship between the stack and canceled stacks.
• Overlooking edge cases such as when all performances are canceled or when no rescheduling is done.

I-mplement

def manage_stage_changes(changes):
    stack = []
    canceled = []

    for change in changes:
        if change.startswith("Schedule"):
            _, performance_id = change.split()
            stack.append(performance_id)
        elif change == "Cancel" and stack:
            canceled.append(stack.pop())
        elif change == "Reschedule" and canceled:
            stack.append(canceled.pop())

    return stack

# Example usage
print(manage_stage_changes(["Schedule A", "Schedule B", "Cancel", "Schedule C", "Reschedule", "Schedule D"]))  
# Output: ["A", "C", "B", "D"]

print(manage_stage_changes(["Schedule A", "Cancel", "Schedule B", "Cancel", "Reschedule", "Cancel"])) 
# Output: []

print(manage_stage_changes(["Schedule X", "Schedule Y", "Cancel", "Cancel", "Schedule Z"])) 
# Output: ["Z"]