Reverse Watchlist - codepath/compsci_guides GitHub Wiki

TIP102 Unit 3 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 input to the problem?
  • A: The input is a list watchlist representing a list of shows sorted by popularity.
• Q: What is the output?
  • A: The output is the watchlist reversed, with the least popular shows first and the most popular shows last.
• Q: How should the reversal be implemented?
  • A: The reversal should be done in-place using the two-pointer technique without using list slicing.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use two pointers to swap elements from the beginning and the end of the list, working towards the center to reverse the list in-place.

1. Initialize two pointers: `left` at the start of the list (index 0) and `right` at the end of the list (index `len(watchlist) - 1`).
2. While the `left` pointer is less than the `right` pointer:
   1. Swap the elements at the `left` and `right` pointers.
   2. Move the `left` pointer one step to the right.
   3. Move the `right` pointer one step to the left.
3. Continue this process until the two pointers meet or cross, at which point the list will be fully reversed.
4. Return the reversed `watchlist`.

⚠️ Common Mistakes

• Forgetting to move the pointers after swapping, which can cause an infinite loop.
• Accidentally creating a new list instead of reversing the original list in-place.
• Not considering edge cases like an empty list or a list with a single element.

I-mplement

def reverse_watchlist(watchlist):
    # Initialize two pointers
    left = 0
    right = len(watchlist) - 1
    
    # Loop until the two pointers meet
    while left < right:
        # Swap the elements at the left and right pointers
        watchlist[left], watchlist[right] = watchlist[right], watchlist[left]
        # Move the pointers towards the center
        left += 1
        right -= 1
    
    return watchlist