Trending Meme Pairs - codepath/compsci_guides GitHub Wiki

Unit 4 Session 1 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 structure of the input?

  • A: The input is a list of lists, where each inner list contains strings representing memes in a single post.

• Q: What is the output?

  • A: The output is a list of tuples, where each tuple contains two memes that frequently appear together across multiple posts.

• Q: What should the function return if there are no frequent pairs?

  • A: The function should return an empty list.

• Q: How should the function handle posts with only one meme?

  • A: Posts with only one meme should be ignored when generating pairs, as they do not contribute to any pairs.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Iterate through each post to generate all possible pairs of memes within the post, count how often each pair appears, and then identify and return the pairs that appear more than once.

1) Initialize an empty dictionary called `pair_count` to keep track of how many times each pair of memes appears together.
2) For each post in the list `meme_posts`:
   a) Iterate through each meme in the post to generate all possible pairs with other memes in the same post.
   b) Ensure that each pair is stored in alphabetical order to avoid duplicates in different order.
   c) Add each pair to the dictionary `pair_count`, incrementing the count if it already exists.
3) After processing all posts, iterate through the `pair_count` dictionary and collect pairs that have a count greater than one.
4) Return the list of trending pairs.

**⚠️ Common Mistakes**

- Generating duplicate pairs or self-pairs, which leads to incorrect frequency counts.
- Not ensuring pairs are stored in a consistent order, which can cause the same pair to be counted multiple times in different orders.

I-mplement

def find_trending_meme_pairs(meme_posts):
    pair_count = {}

    for post in meme_posts:
        for i in range(len(post)):
            for j in range(i + 1, len(post)):
                meme1 = post[i]
                meme2 = post[j]
                # Ensure pair is always in alphabetical order
                if meme1 > meme2:
                    meme1, meme2 = meme2, meme1
                pair = (meme1, meme2)
                if pair in pair_count:
                    pair_count[pair] += 1
                else:
                    pair_count[pair] = 1

    # Collect pairs that appear more than once
    trending_pairs = []
    for pair, count in pair_count.items():
        if count > 1:
            trending_pairs.append(pair)

    return trending_pairs