Identify Repeated Themes - codepath/compsci_guides GitHub Wiki

Unit 4 Session 2 Advanced (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 and return themes that appear more than once across different scenes.
• Q: What are the inputs?
  • A: The input is a list of dictionaries, where each dictionary represents a scene with an associated theme.
• Q: What are the outputs?
  • A: The output is a list of themes that occur more than once across the scenes.
• Q: How should the themes be tracked?
  • A: Track the occurrence of each theme using a dictionary and then extract the themes that have a count greater than one.
• Q: Are there any assumptions about the input?
  • A: The input list is well-formed with each scene containing a "scene" and "theme" key, and the values are strings.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a dictionary to count the frequency of each theme. After counting, extract and return the themes that have a count greater than one.

1) Initialize an empty dictionary `theme_count` to track the frequency of each theme.
2) Iterate through the `scenes` list:
   a) Extract the theme from each scene and update its count in `theme_count`.
3) Create a list `repeated_themes` containing themes that have a count greater than one.
4) Return the `repeated_themes` list.

**⚠️ Common Mistakes**

- Forgetting to correctly update the count for each theme, leading to incorrect identification of repeated themes.
- Assuming that all themes are unique without handling cases where themes appear more than once.
- Not considering that the input might contain no repeated themes, which should result in an empty list being returned.

I-mplement

def identify_repeated_themes(scenes):
    theme_count = {}

    # Count the occurrences of each theme
    for scene in scenes:
        theme = scene["theme"]
        if theme in theme_count:
            theme_count[theme] += 1
        else:
            theme_count[theme] = 1

    # Extract themes that appear more than once
    repeated_themes = [theme for theme, count in theme_count.items() if count > 1]

    return repeated_themes

Example Usage:

scenes = [
    {"scene": "The hero enters the dark forest.", "theme": "courage"},
    {"scene": "A mysterious figure appears.", "theme": "mystery"},
    {"scene": "The hero faces his fears.", "theme": "courage"},
    {"scene": "An eerie silence fills the air.", "theme": "mystery"},
    {"scene": "The hero finds a hidden treasure.", "theme": "discovery"}
]

repeated_themes = identify_repeated_themes(scenes)
print(repeated_themes)  
# Output: ['courage', 'mystery']

scenes = [
    {"scene": "The spaceship lands on an alien planet.", "theme": "exploration"},
    {"scene": "A strange creature approaches.", "theme": "danger"},
    {"scene": "The crew explores the new world.", "theme": "exploration"},
    {"scene": "The crew encounters hostile forces.", "theme": "conflict"},
    {"scene": "The crew makes a narrow escape.", "theme": "danger"}
]

repeated_themes = identify_repeated_themes(scenes)
print(repeated_themes)  
# Output: ['exploration', 'danger']