How Can You Reverse Words in a String?

Reversing words in a string is a common task in programming. This question often appears in technical interviews to assess a candidate's problem-solving skills, understanding of strings, and ability to manipulate data.

Why Reverse Words?

Reversing words is a good exercise to practice string manipulation, which is fundamental in many programming languages. This task helps interviewers see how you approach problem-solving and how you organize your code.

The Problem Defined

The typical problem statement is simple: given a string, reverse the order of the words. For example, if the input is:

1"The quick brown fox"

The output should be:

1"fox brown quick The"

Spaces between words must be maintained, and extra spaces at the ends should not affect the output.

Simple Steps to Solve the Problem

1. Trim the String: Start by removing any leading or trailing whitespace.
2. Split the String: Use a method to split the string into words based on spaces.
3. Reverse the Order: Reverse the list of words.
4. Join the Words: Join the words back into a single string, separating them with a space.

Example Interview Questions

Interviewers may ask various questions related to reversing words in a string. Here are some example questions along with explanations on how to approach them.

Question 1: Reverse Words in a Simple String

Example: Write a function that takes in a string and returns the string with the words reversed.

1def reverse_words(s):
2    # Step 1: Trim the string
3    s = s.strip()
4    
5    # Step 2: Split the string into words
6    words = s.split()
7    
8    # Step 3: Reverse the list of words
9    words.reverse()
10    
11    # Step 4: Join the words back into a string
12    return ' '.join(words)
13
14# Example Call
15print(reverse_words("The quick brown fox"))  # Output: "fox brown quick The"

Question 2: Handle Extra Spaces

Example: Modify the function to handle cases with extra spaces between words or at the ends.

1def reverse_words(s):
2    # Trim and split while removing extra spaces
3    words = s.split()
4    
5    # Reverse the list of words
6    words.reverse()
7    
8    # Join the words back into a string
9    return ' '.join(words)
10
11# Example Call
12print(reverse_words("  The   quick brown   fox  "))  # Output: "fox brown quick The"

Question 3: In-Place Reversal of Words (Advanced)

Example: Can you reverse the words in the string in place without using extra space?

1def reverse_words(s):
2    # Convert string to a list of characters as strings are immutable
3    s = list(s)
4    
5    # Helper function to reverse a portion of the list
6    def reverse_range(start, end):
7        while start < end:
8            s[start], s[end] = s[end], s[start]
9            start += 1
10            end -= 1
11    
12    # Step 1: Reverse the entire string
13    reverse_range(0, len(s) - 1)
14    
15    # Step 2: Reverse each word in the string
16    start = 0
17    for end in range(len(s)):
18        if s[end] == ' ':
19            reverse_range(start, end - 1)
20            start = end + 1
21    reverse_range(start, len(s) - 1)  # reverse the last word
22
23    return ''.join(s)
24
25# Example Call
26print(reverse_words("The quick brown fox"))  # Output: "fox brown quick The"

Question 4: Performance Considerations

Example: Discuss the time and space complexity of your algorithm.

In the above implementations:

• The time complexity is O(n), where n is the number of characters in the string. This includes the time spent splitting and joining the string.
• The space complexity is also O(n) because of the storage used for the list of words or characters.

Practicing reversing words will enhance your string manipulation skills. Implement alternate methods, and think about edge cases to improve your coding acumen. This task is not just about coding; it demonstrates how you think and approach problems – qualities that every interviewer appreciates.