Find Recent Podcast Episodes - 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 retrieve the most recent n podcast episodes from a list, in the order they were added.
• Q: What are the inputs?
  • A: The input is a list of episode IDs and an integer n representing the number of most recent episodes to retrieve.
• Q: What are the outputs?
  • A: The output is a list of the most recent n episode IDs in the reverse order of their addition.
• Q: How should the function behave if n is greater than the number of episodes?
  • A: If n is greater than the number of episodes, return all episodes in reverse order.
• Q: What should happen if the list of episodes is empty?
  • A: If the list of episodes is empty, return an empty list.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a stack to collect the episodes in the order they are added. Then, pop the most recent n episodes from the stack to retrieve them in reverse order.

1) Initialize an empty list `stack`.
2) Iterate through the `episodes` list and push each episode onto the `stack`.
3) Initialize an empty list `recent_episodes`.
4) While `n` is greater than 0 and the stack is not empty:
   a) Pop the top element from the stack and add it to `recent_episodes`.
   b) Decrement `n` by 1.
5) Return `recent_episodes`, which now contains the most recent `n` episodes in the reverse order of their addition.

**⚠️ Common Mistakes**

- Forgetting to handle the case where `n` is greater than the number of episodes.
- Not reversing the order of the retrieved episodes.
- Assuming the list of episodes will always have at least `n` elements.

I-mplement

def get_recent_episodes(episodes, n):
    stack = []

    # Push all episodes onto the stack
    for episode in episodes:
        stack.append(episode)

    # Pop the most recent `n` episodes
    recent_episodes = []
    while n > 0 and stack:
        recent_episodes.append(stack.pop())
        n -= 1

    return recent_episodes

Example Usage:

episodes1 = ['episode1', 'episode2', 'episode3', 'episode4']
n = 3
print(get_recent_episodes(episodes1, n))  
# Output: ['episode4', 'episode3', 'episode2']

episodes2 = ['ep1', 'ep2', 'ep3']
n = 2
print(get_recent_episodes(episodes2, n))  
# Output: ['ep3', 'ep2']

episodes3 = ['a', 'b', 'c', 'd']
n = 5
print(get_recent_episodes(episodes3, n))  
# Output: ['d', 'c', 'b', 'a']