Find Most Frequent 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 determine the episode length that occurs most frequently in a given list of episode lengths.
• 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 episode length that occurs most frequently. If there is a tie, return the smallest length among those with the highest frequency.
• Q: How should ties be handled?
  • A: If multiple lengths have the same highest frequency, return the smallest length.
• 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: Use a dictionary to count the frequency of each episode length. Then, identify the length with the highest frequency. In case of a tie, return the smallest length among those with the highest frequency.

1) Initialize an empty dictionary `frequency_map` to store the frequency of each episode length.
2) Iterate through the `episode_lengths` list:
   a) For each length, increment its count in `frequency_map`.
3) Initialize `max_frequency` to 0 and `most_frequent` to a large number.
4) Iterate through the `frequency_map`:
   a) If the current length's frequency is higher than `max_frequency`, update `max_frequency` and set `most_frequent` to this length.
   b) If the current length's frequency is equal to `max_frequency` but the length is smaller than `most_frequent`, update `most_frequent`.
5) Return `most_frequent`.

**⚠️ Common Mistakes**

- Forgetting to correctly handle ties, resulting in the incorrect length being returned.
- Not initializing or updating the frequency map properly, leading to incorrect counts.
- Assuming that there will always be a unique most frequent length without considering ties.

I-mplement

def most_frequent_length(episode_lengths):
    frequency_map = {}

    # Count frequencies of each length
    for length in episode_lengths:
        if length in frequency_map:
            frequency_map[length] += 1
        else:
            frequency_map[length] = 1

    # Find the most frequent length
    max_frequency = 0
    most_frequent = float('inf')

    for length, frequency in frequency_map.items():
        if frequency > max_frequency or (frequency == max_frequency and length < most_frequent):
            max_frequency = frequency
            most_frequent = length

    return most_frequent

Example Usage:

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

print(most_frequent_length([20, 20, 30, 30, 40, 40, 40]))  
# Output: 40

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