Reverse a Sentence
You are given an array of characters arrthat consists of sequences of characters separated by space characters. Each space-delimited sequence of characters defines a word. Implement a function reverseWords that reverses the order of the words in the array in the most efficient manner.
Explain your solution and analyze its time and space complexities.
Example
input: arr = [ 'p', 'e', 'r', 'f', 'e', 'c', 't', ' ', 'm', 'a', 'k', 'e', 's', ' ', 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e' ] output: [ 'p', 'r', 'a', 'c', 't', 'i', 'c', 'e', ' ', 'm', 'a', 'k', 'e', 's', ' ', 'p', 'e', 'r', 'f', 'e', 'c', 't' ]
Even if your language of choice enables this, don't be tempted to use standard functions. Consider how inefficient it is to separately create a string, split the words, and reverse the split.
As a general rule, if you're tempted to use a standard or library function, be sure to explain that function's time and space complexity before committing to that solution. You may find a more efficient way to solve the problem yourself. Oftentimes in coding interviews, this is the whole point of the exercise.
How have you handled edge cases? For example, empty arrays, arrays with nothing but spaces, arrays with single words only, or with multiple spaces between words, etc.
Were you able to achieve a linear time complexity and a constant space complexity?
Bonus: how might the mirrorReverse function be implemented with a single index?
One possible solution is doing a linear iteration on arr while pushing a copy of every word to a stack and then pulling them in reverse order while copying the words back into arr. Another approach is initializing a new array at the same length, iterating over arr from right to left, and copying any sequence of characters to the new array from left to right. Both approaches take O(N) time and at least O(N) space.
A more elegant and efficient approach is to reverse all the characters in arr and then reverse the characters in each word separately. While the first reverse gives us the words in the reverse order as we wanted, it also reverses the characters of each word. To fix that, we do the second
reverse, which reverses each word separately.
Reversing items in an array is done by a 'mirror' function, that swaps the items of every 2 indices with the same distance from the middle.
Pseudocode:
function reverseWords(arr): # reverse all characters: n = arr.length mirrorReverse(arr, 0, n-1) # reverse each word: wordStart = null for i from 0 to n-1: if (arr[i] == ' '): if (wordStart != null): mirrorReverse(arr, wordStart, i-1) wordStart = null else if (i == n-1): if (wordStart != null): mirrorReverse(arr, wordStart, i) else: if (wordStart == null): wordStart = i return arr # helper function - reverses the order of items in arr # please note that this is language dependent: # if are arrays sent by value, reversing should be done in place function mirrorReverse(arr, start, end): tmp = null while (start < end): tmp = arr[start] arr[start] = arr[end] arr[end] = tmp start++ end--
Time Complexity: traversing the array twice with a constant number of actions for each item is linear O(N).
Space Complexity: using iteration indices and one temp variable takes constant O(1) memory.
Answer to bonus question: The mirrorReverse function could be implemented with a single index with left to right linear iteration and swapping arr[i] and arr[n-1-i] as long as i < n-1-i.
def reverse_words(arr):
# Reverse all characters
n = len(arr)
mirror_reverse(arr, 0, n - 1)
# Reverse each word
word_start = None
for i in range(n):
if arr[i] == ' ':
if word_start is not None:
mirror_reverse(arr, word_start, i - 1)
word_start = None
elif i == n - 1:
if word_start is not None:
mirror_reverse(arr, word_start, i)
else:
if word_start is None:
word_start = i
return arr
# Helper function - reverses the order of items in arr
# Please note that this is language dependent:
# If arrays are passed by value, reversing should be done in place
def mirror_reverse(arr, start, end):
while start < end:
arr[start], arr[end] = arr[end], arr[start]
start += 1
end -= 1
#inplace reversal without inbuilt functions def reverseString(s): chars = list(s) l, r = 0, len(s)-1 while l < r: chars[l],chars[r] = chars[r],chars[l] l += 1 r -= 1 reversed = "".join(chars) return reversed