Meme Trend Identification - codepath/compsci_guides GitHub Wiki

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 30 mins
• 🛠️ Topics: Arrays, Hashmaps

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is a "trending" meme?
  • A: A meme is considered "trending" if it appears more than once in the input list.
• Q: What should be returned?
  • A: Return a list of memes that are considered trending.
• Q: Are there any constraints on the size or type of the input?
  • A: The input will be a list of strings, each string representing a meme.

HAPPY CASE
Input: ["Dogecoin to the moon!", "One does not simply walk into Mordor", "Dogecoin to the moon!", "Distracted boyfriend", "One does not simply walk into Mordor"]
Output: ['Dogecoin to the moon!', 'One does not simply walk into Mordor']
Explanation: Both "Dogecoin to the moon!" and "One does not simply walk into Mordor" appear more than once.

EDGE CASE
Input: ["Y U No?", "First world problems", "Philosoraptor", "Bad Luck Brian"]
Output: []
Explanation: None of the memes appear more than once.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

This problem can be categorized under:

• Hashmaps: A hashmap (or dictionary) can be used to count the occurrences of each meme.
• Arrays: The input is a list of memes, and we need to process each meme in the list.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
We need to count how many times each meme appears in the input list. If a meme appears more than once, we consider it a "trending" meme. We can store the counts in a dictionary and then iterate through the dictionary to find memes that have a count greater than 1.

1) Initialize an empty dictionary `meme_count` to store the counts of each meme.
2) Loop through the input list of memes:
    a) If the meme is already in the dictionary, increment its count.
    b) If the meme is not in the dictionary, add it with a count of 1.
3) Initialize an empty list `trending_memes`.
4) Loop through the dictionary:
    a) If the count of a meme is greater than 1, add it to the `trending_memes` list.
5) Return the `trending_memes` list.

⚠️ Common Mistakes

• Forgetting to handle the case where no memes appear more than once.
• Not using the correct data structure for counting (e.g., using a list instead of a dictionary).

4: I-mplement

Implement the code to solve the algorithm.

def find_trending_memes(memes):
    meme_count = {}
    trending_memes = []

    for meme in memes:
        if meme in meme_count:
            meme_count[meme] += 1
        else:
            meme_count[meme] = 1

    for meme, count in meme_count.items():
        if count > 1:
            trending_memes.append(meme)

    return trending_memes

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Example 1:

Input: ["Dogecoin to the moon!", "One does not simply walk into Mordor", "Dogecoin to the moon!", "Distracted boyfriend", "One does not simply walk into Mordor"]
meme_count = {"Dogecoin to the moon!": 2, "One does not simply walk into Mordor": 2, "Distracted boyfriend": 1}
trending_memes = ['Dogecoin to the moon!', 'One does not simply walk into Mordor']
Output: ['Dogecoin to the moon!', 'One does not simply walk into Mordor']

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Let N represent the number of memes in the input list.

• Time Complexity: O(N) because we iterate through the input list once to count the memes and then iterate through the dictionary to find the trending memes. Both operations take linear time.
• Space Complexity: O(N) because we store the counts of each meme in a dictionary, which can take up to N space if all memes are unique.