Post Editor - 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 needs to be reversed in the post?
  • A: The order of characters in each word within the post should be reversed.
• Q: Should the order of the words themselves be changed?
  • A: No, the order of the words should remain the same; only the characters within each word should be reversed.
• Q: How should spaces be handled?
  • A: Spaces should be preserved in their original positions.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a queue to reverse the characters of each word while preserving the spaces and word order.

1. Initialize an empty deque (double-ended queue) to hold the characters of each word.
2. Initialize an empty list to build the final result.
3. Iterate through each character in the post:
   1. If the character is not a space, enqueue it to the deque.
   2. If the character is a space, dequeue all characters from the deque (which reverses the word) and append them to the result list. Then append the space to the result list.
4. After the loop, handle any remaining characters in the deque (i.e., the last word).
5. Join all elements in the result list to form the final string and return it.

⚠️ Common Mistakes

• Forgetting to handle the last word if the post does not end with a space.
• Accidentally reversing the entire string instead of just the characters within each word.
• Not preserving the spaces in their original positions.

I-mplement

from collections import deque

def edit_post(post):
    queue = deque()
    result = []
    
    for char in post:
        if char != ' ':
            queue.append(char)  # Enqueue character
        else:
            while queue:
                result.append(queue.pop())  # Dequeue to reverse the word
            result.append(' ')  # Add the space back after the word is reversed
    
    # Handle the last word (if the string doesn't end with a space)
    while queue:
        result.append(queue.pop())
    
    return ''.join(result)