Reverse the words in a sentence.
We can define a word as any substring separated by one or more spaces. To do this on constant space, simply reverse the entire sentence, and then reverse each word within.
In haskell, the recursive solution would be:
reverse_words :: [Char] -> [Char] reverse_words  =  reverse_words xs = initial_spaces ++ (reverse after_spaces) ++ reverse_words remaining where initial_spaces = takeWhile isSpace xs spaces_dropped = dropWhile isSpace xs after_spaces = takeWhile (\x -> not (isSpace x)) spaces_dropped remaining = drop (length after_spaces) spaces_dropped
This is clearly not O(1) in space usage. The constant space solution would require maintaining array structures and swapping entries within the array.