Meme Popularity Queue - 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 consists of two lists: one containing meme names (strings) and the other containing integers representing the number of times each corresponding meme will be reposted.

• Q: What is the output?

  • A: The output is a list of strings representing the final order in which all reposts of the memes are processed.

• Q: How should reposts be handled?

  • A: Each meme should be added back to the queue after processing if it has remaining reposts.

• Q: What happens if a meme has no reposts?

  • A: It should be processed only once and not re-added to the queue.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a queue to simulate the reposting process. For each meme, process it by appending it to the final order, and if it has remaining reposts, re-add it to the queue.

1) Initialize an empty deque called `queue` and an empty list called `final_order`.
2) Enqueue each meme along with its repost count into the `queue`.
3) While the `queue` is not empty:
   a) Dequeue the first meme and its count.
   b) Append the meme to the `final_order`.
   c) Decrement the repost count.
   d) If the repost count is greater than 0, re-enqueue the meme with the updated count.
4) Return the `final_order` list.

**⚠️ Common Mistakes**

- Forgetting to decrement the repost count before re-enqueuing a meme.
- Mishandling the queue operations, leading to incorrect final orders.

I-mplement

from collections import deque

def simulate_meme_reposts(memes, reposts):
    queue = deque()
    final_order = []

    # Enqueue each meme with its repost count
    for meme, count in zip(memes, reposts):
        queue.append((meme, count))

    # Process the queue
    while queue:
        meme, count = queue.popleft()
        final_order.append(meme)
        count -= 1
        if count > 0:
            queue.append((meme, count))  # Re-enqueue if more reposts are left

    return final_order