Find Unique Genres with Minimum 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 identify unique genres where the shortest episode length is greater than or equal to a specified threshold.
  • Q: What are the inputs?
    • A: The input is a list of tuples where each tuple contains an episode title, genre, and length, along with a threshold value for the minimum episode length.
  • Q: What are the outputs?
    • A: The output is a list of genres that meet the minimum episode length requirement, sorted alphabetically.
  • Q: How should genres with multiple episodes be handled?
    • A: Only include genres where the shortest episode length is greater than or equal to the threshold.
  • Q: What should be done if no genre meets the threshold?
    • A: Return an empty list.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a dictionary to track the shortest episode length for each genre. After iterating through the episodes, filter out genres that do not meet the threshold and return the remaining genres sorted alphabetically.

1) Initialize an empty dictionary `genre_min_length` to store the minimum length for each genre.
2) Iterate through the `episodes` list:
   a) For each `(title, genre, length)` tuple:
      - If the genre is not in `genre_min_length`, add it with the current length.
      - If the genre is in `genre_min_length`, update its value if the current length is shorter.
3) Filter the `genre_min_length` dictionary to keep only the genres where the minimum length is greater than or equal to the threshold.
4) Sort the remaining genres alphabetically and return the sorted list.

**⚠️ Common Mistakes**

- Forgetting to update the minimum length for a genre when a shorter episode is found.
- Not correctly filtering genres based on the threshold.
- Assuming that all genres will have at least one episode meeting the threshold.

I-mplement

def unique_genres_with_min_length(episodes, threshold):
    genre_min_length = {}

    for title, genre, length in episodes:
        if genre not in genre_min_length:
            genre_min_length[genre] = length
        else:
            genre_min_length[genre] = min(genre_min_length[genre], length)

    valid_genres = [genre for genre, min_length in genre_min_length.items() if min_length >= threshold]

    return sorted(valid_genres)

Example Usage:

print(unique_genres_with_min_length([("Episode 1", "Tech", 30), ("Episode 2", "Health", 45), ("Episode 3", "Tech", 35), ("Episode 4", "Entertainment", 60)], 30))  
# Output: ['Entertainment', 'Health', 'Tech']

print(unique_genres_with_min_length([("Episode A", "Science", 40), ("Episode B", "Science", 50), ("Episode C", "Art", 25), ("Episode D", "Art", 30)], 30))  
# Output: ['Art', 'Science']

print(unique_genres_with_min_length([("Episode X", "Music", 20), ("Episode Y", "Music", 15), ("Episode Z", "Drama", 25)], 20))  
# Output: ['Drama', 'Music']