Find Median Episode Length - codepath/compsci_guides GitHub Wiki

Unit 4 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 goal of the problem?
  • A: The goal is to find the median episode length from a given list of episode durations.
• Q: What are the inputs?
  • A: The input is a list of integers where each integer represents the length of a podcast episode in minutes.
• Q: What are the outputs?
  • A: The output is the median episode length. If the list has an odd number of elements, return the middle value. If it has an even number of elements, return the average of the two middle values.
• Q: How should the median be calculated?
  • A: First, sort the list of episode durations. Then, depending on whether the list length is odd or even, return the appropriate median value.
• Q: Are there any assumptions about the input?
  • A: The list contains valid, non-negative integers representing episode lengths.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Sort the list of episode durations, then calculate the median based on the length of the sorted list.

1) Sort the `durations` list in ascending order.
2) Find the middle index `mid` as `n // 2`, where `n` is the length of the sorted list.
3) If the list length `n` is odd, return the element at index `mid`.
4) If the list length `n` is even, return the average of the elements at indices `mid - 1` and `mid`.

**⚠️ Common Mistakes**

- Forgetting to sort the list before finding the median, leading to incorrect results.
- Not handling the case where the list length is even, which requires calculating the average of two middle values.
- Assuming the list has an odd number of elements without considering even-length lists.

I-mplement

def find_median_episode_length(durations):
    # Sort the list of durations
    sorted_durations = sorted(durations)

    # Find the middle index
    n = len(sorted_durations)
    mid = n // 2

    # Calculate the median
    if n % 2 == 1:
        # Odd length, return the middle element
        return sorted_durations[mid]
    else:
        # Even length, return the average of the two middle elements
        return (sorted_durations[mid - 1] + sorted_durations[mid]) / 2

Example Usage:

print(find_median_episode_length([45, 30, 60, 30, 90]))  
# Output: 45

print(find_median_episode_length([90, 80, 60, 70, 50]))  
# Output: 70

print(find_median_episode_length([30, 10, 20, 40, 30, 50]))  
# Output: 30.0