Merge Performance Schedules - 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 consists of two strings, schedule1 and schedule2, where each character represents a performance slot.
  • Q: What is the output?
    • A: The output is a merged string of the two schedules, where performances from schedule1 and schedule2 are added in alternating order, starting with schedule1.
  • Q: What happens if the schedules have different lengths?
    • A: If one schedule is longer than the other, the remaining performances from the longer schedule are appended to the end of the merged schedule.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a loop to alternate between adding characters from schedule1 and schedule2 to the merged schedule. If one schedule runs out of characters, append the remaining characters from the other schedule.

1. Initialize an empty list `merged_schedule` to store the characters of the merged schedule.
2. Initialize two pointers `i` and `j` to `0` to track the current position in `schedule1` and `schedule2`, respectively.
3. Iterate while both pointers are within the bounds of their respective schedules:
   1. Append the character from `schedule1` at index `i` to `merged_schedule`.
   2. Append the character from `schedule2` at index `j` to `merged_schedule`.
   3. Increment both pointers.
4. After the loop, check if there are remaining characters in either schedule:
   1. If there are remaining characters in `schedule1`, append them to `merged_schedule`.
   2. If there are remaining characters in `schedule2`, append them to `merged_schedule`.
5. Convert `merged_schedule` to a string and return it.

⚠️ Common Mistakes

  • Not handling the case where one schedule is longer than the other correctly, leading to incomplete merging.
  • Incorrectly managing the alternation between the two schedules.
  • Forgetting to convert the merged list back to a string before returning.

I-mplement

def merge_schedules(schedule1, schedule2):
    merged_schedule = []
    i, j = 0, 0

    # Merge performances from both schedules alternately
    while i < len(schedule1) and j < len(schedule2):
        merged_schedule.append(schedule1[i])
        merged_schedule.append(schedule2[j])
        i += 1
        j += 1

    # Append remaining performances from schedule1 or schedule2
    if i < len(schedule1):
        merged_schedule.append(schedule1[i:])
    if j < len(schedule2):
        merged_schedule.append(schedule2[j:])

    return ''.join(merged_schedule)

# Example usage
print(merge_schedules("abc", "pqr"))  # Output: "apbqcr"
print(merge_schedules("ab", "pqrs"))  # Output: "apbqrs"
print(merge_schedules("abcd", "pq"))  # Output: "apbqcd"