Reversing Deli Orders - codepath/compsci_guides GitHub Wiki

TIP102 Unit 7 Session 1 Advanced (Click for link to problem statements)

Problem 2: Reversing Deli Orders

The deli counter is busy, and orders have piled up. To serve the last customer first, you need to reverse the order of the deli orders. Given a string orders where each individual order is separated by a single space, write a recursive function reverse_orders() that returns a new string with the orders reversed.

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 15-20 mins
  • 🛠️ Topics: Recursion, String Manipulation, List Operations

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: What is the main task in this problem?
    • A: The task is to reverse the order of words in a string using a recursive function.
  • Q: What should the function return if the string is empty?
    • A: The function should return an empty string.
HAPPY CASE
Input: "Bagel Sandwich Coffee"
Output: "Coffee Sandwich Bagel"
Explanation: The words "Bagel Sandwich Coffee" are reversed to "Coffee Sandwich Bagel".

EDGE CASE
Input: "
Output: "
Explanation: An empty string returns an empty string.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Reversing Words in a String, we want to consider the following approaches:

  • Recursive String Reversal: Use recursion to reverse the list of words and then join them back together.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • Split the string into a list of words and use a helper function to recursively reverse the list. The base cases handle when there are no words or only one word left.

Recursive Approach:

1) Base case: If the list `words` is empty, return an empty string.
2) Base case: If the list `words` has only one word, return that word.
3) Recursive case: Call the helper function on the rest of the list `words[1:]` and append the first word at the end.

⚠️ Common Mistakes

  • Forgetting to handle the base cases correctly, which can result in incorrect results or infinite recursion.
  • Incorrectly managing the string concatenation, leading to extra spaces or incorrect order.

4: I-mplement

Implement the code to solve the algorithm.

def reverse_helper(words):
    if len(words) == 0:  # Base case: no words left to process
        return "
    if len(words) == 1:  # Base case: only one word left
        return words[0]
    # Recursive case: reverse the rest and append the first word at the end
    return reverse_helper(words[1:]) + " " + words[0]

def reverse_orders(orders):
    words = orders.split()  # Split the sentence into a list of words
    return reverse_helper(words)  # Call the external helper function with the list of words

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Trace through the reverse_orders function with the input "Bagel Sandwich Coffee". The function should return "Coffee Sandwich Bagel" after reversing the order of words.
  • Test the function with edge cases like an empty string ". The function should return ", correctly handling the base case.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Time Complexity:

  • Time Complexity: O(N) where N is the number of words in the string. The function processes each word exactly once.
  • Space Complexity: O(N) due to the recursion stack and the space needed to store the reversed string. The depth of recursion is proportional to the number of words.

Discussion:

  • The recursive approach effectively handles the task of reversing the order of words in the string. It is straightforward and aligns well with the recursive nature of the problem.
  • While the recursive approach is clear and elegant, an iterative approach might be more efficient in practice, particularly in terms of space usage.