[Challenge] Reverse Words

Events & Challenges
1

#Code Challenge: May 3, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview, similar to the FizzBuzz Challenge often used at places like Facebook and Google.

For this week’s challenge, inspired by a question reported to have been asked in developer job interviews at Microsoft (and also inspired by Yoda in honor of Star Wars Day!):

Write a function that will take a given string and reverse the order of the words. “Hello world” becomes “world Hello” and “May the Fourth be with you” becomes “you with be Fourth the May”

You may assume that the string is a sentence that contains only letters and spaces, with all words separated by one space.

If you find this challenge easy, that’s actually not unusual in interview situations, but interviewers often ask you to not only thoroughly explain your process but to up your game in an extension to the initial challenge, so you should definitely try for extra credit (see below)!

####Scroll down and reply to this thread with your code to participate! Don’t just submit your code, remember to explain your solution, too! If you want your entry to be considered under our “best code” assessment, you must link to your code running on repl.it to make assessing your entry easier (see below).

##Extra Credit

###Intermediate difficulty

The string in question now has punctuation, for example “Hello world!” and “With you, be May the Fourth” Write a function to reverse the order of words, but keep the punctuation in place. For example, turn "Hello world!" into “world Hello!” and “With you, be May the Fourth.” to “Fourth the, May be you With.”

In the case of multiple consecutive punctuation marks or multiple consecutive whitespace characters, deal with them as you see fit.

This week, our easy level challenge is a little easier than normal, so only submissions at intermediate level and above will be eligible to “win” this challenge.

###Hard Difficulty
If you’d like to go even further:

Can you solve the initial challenge (without punctuation) in-place without using additional data structures, and with the time complexity being O(n)? Can you do the same for the intermediate level challenge (including punctuation)?

Learn more about Big O notation and time complexity here and here. There’s also an old (and thus unsupported) Codecademy course on Big O, if you prefer.

#The Winners
See the full list and feedback here.

##How to participate

  • Use any language taught on Codecademy (Python, Java, Ruby, JavaScript, PHP, etc.)

  • Submissions in C++, C, or other languages not taught on Codecademy are welcomed, but these may not be eligible to “win” as a featured submission (see below)

  • Please include a link to your code running on repl.it, or as a backup CodePen, JSFiddle, or CodeBits so that our team (and your fellow students) can assess your submission easier and faster - if we have dozens of submissions, we will not have time to assess entries that do not have links in this manner.

  • If you want to post your code directly, please make sure that it is correctly formatted!

  • The best submission or submissions will be featured here on the forums and via various social media channels (like our Twitter)

  • Solutions submitted before 6:00pm in New York City on the Friday immediately following the code challenge are eligible for consideration as a featured “best entry.”

  • Some of the criteria we use to judge a “best submission” are the simplicity, elegance, creativity, and efficiency of your submission. Languages like Python will often have an advantage over languages like JavaScript, so we’ll take that into account when judging a winner - the “best” entry or entries may not all be the fastest or most efficient.

  • To be considered as a “best submission,” you must explain your thought processes in making your answer: how and why you designed your function the way you did. This way, we’ll be more sure that you came up with your own solution, but crucially this is part of the reason why this type of question is asked in job interviews.

####Happy coding!

The fine print:

  • Remember, the point of code challenges like these is to test and stretch yourself with an unusual problem, so don’t be dissuaded if you find it difficult or don’t know where to start! Start with Googling, but see if you can find out how to think about the problem and what tools you need to solve it, but don’t just go looking for the solution itself. This way, it’ll be a better learning exercise for you - developers can’t always find and copy “the right answer” online, which is why questions like these are used in developer job interviews! Interviewers want to be able to see how you think through problems and not just whether or not you can solve them.
  • If you are interested in “winning” the code challenge, please don’t use any unusual repos or anything that will make it difficult for us or your fellow users to assess your answer quickly.
  • Do you have a code challenge to share with other users? Issue it! Make a new topic with [Challenge] in the title to open a challenge, maybe we’ll even feature it in our next newsletter!
2

Yaay I get to be first! :smile:

Beginner Difficulty:

https://repl.it/Hdjx/1

Nifty One Liner. :wink:

Intermediate / Hard Difficulty:
https://repl.it/HdnD/1

5 Likes
3

Beginner Difficulty:

https://codepen.io/keefyboooo/pen/BRdjRR

function reverseString(string) {
  var words = string.split(' ').reverse().join(' ');
  
  document.body.innerHTML += words;
}

reverseString('May the Fourth be with you');

I have turned the string into an array, reversed it, then joined it back together

4 
def str_reverse(text):
    ''' function to reverse the words in a string '''

    # split text on spaces and store in a list
    lst = text.split(sep=' ')

    # step through the list in reverse order
    rev = lst[::-1]

    # join reversed list with a space between words to produce final string
    return ' '.join(rev)


print(str_reverse('Hello world'))
5

def reverseString(string)
words = string.split(" “).reverse.join(” ")
end

https://repl.it/HeEu/0

6

Rather than loop through the string and add a space, you should just be able to perform a .join(’ '); on your array with the separator defined as a space to convert the array back to a string with each element of that array separated by the space.

8

https://repl.it/embed/HeFX/12.js

9 
let string = "May the Fourth be with you";
let stringAsArray = string.split(' ').reverse();
let newString = stringAsArray.join(' ');
document.body.textContent = newString;
11

Here’s my try with JavaScript.

I used the string split method to transform the string into an array of elements, by inserting a “,” wherever a space appeared, then I used a simple for loop to counter backwards and write the words from the last itens to the first in the document, there was a bug with the length of the array, I just subtract one from the array.length to fix it.

See the Pen YVxWWJ by Francisco Santos (@FrankZang) on CodePen.

12

My first time commenting a solution. Beginner style

Private Function ReverseString(ByVal targetString As String) As String
        Dim textArray As String() = Split(targetString, " ")
        Dim reverseText As String = ""

        For i As Integer = (textArray.Length - 1) To 0 Step -1
            reverseText += (textArray(i) + " ")
        Next

        Return reverseText
    End Function
1 Like
13

Beginner:

#!/usr/bin/env perl
use 5.18.0;
say join(" ", reverse(split(/ /, "Codeacademy is really cool")));

Intermediate/Hard:

#!/usr/bin/env perl

use 5.018;

my @tokens = split /\b/, "With you, be May the Fourth.";

my ($left, $right) = (0, $#tokens);

while ($left < $right) {
    ++$left  while ($left < $right && $tokens[$left]  =~ /\W/);
    --$right while ($left < $right && $tokens[$right] =~ /\W/);
    @tokens[$left, $right] = @tokens[$right, $left];
    ++$left;
    --$right;
}

say @tokens;

First I split the string on “word boundaries” (/\b/), which splits the example string like this:

 0  'With'
 1  ' '
 2  'you'
 3  ', '
 4  'be'
 5  ' '
 6  'May'
 7  ' '
 8  'the'
 9  ' '
10  'Fourth'
11  '.'

Then I initialize two index variables ($left and $right) pointing to the first and last token respectivelly.

Then I move the left index to the right and the right index to the left until both point to words, making sure they don’t pass over each other. In this situation I swap the words and try to move the indexes again to find the next pair of words.

When the index pass each other I print the @tokens array, which had its words swapped as required.

14 
function reverseThis(sentence) {
   var result = sentence.split(" ").reverse().join(" ");
   return result;
}

https://repl.it/HeJM/0

15

oh yeah, thanks. Updated.

Might try and get it working with punctuation too.

16 
// Easy
function reverseString(s) {
	return s.split(" ").reverse().join(" ");
}

console.assert(reverseString('Hi there mate') === 'mate there Hi', 'Sentences do not match');

// Intermediate 
function reverseStringV2(s) {
  const punctuationInString = s.split(" ").map((word) => word.replace(/[^.,\/#!$%\^&\*;:{}=\-_`~()]/g, ""));
	return s.split(" ").map((word) => word.replace(/[.,\/#!$%\^&\*;:{}=\-_`~()]/g, "")).reverse().map((word, index) => word.concat(punctuationInString [index])).join(" ");
}

console.assert(reverseStringV2('With you, be May the Fourth.') === 'Fourth the, May be you With.', 'Sentences do not match');

For easy I split the string in to an array, reverse it and join it back up again where each word is joined with a space.

For intermediate I create a new array of just the punctuation in the given string by negating a regex to rip out of characters that are not considered punctuation. Then I take the original string and turn it in to an array. Then I map over and remove all the punctuation. I reverse the order and map over again and concat the punctuation to its correct place on to the new words. This is done using the punctuationInString array. Since the two arrays will always be the same size you I could simply concat by the index of the word in the array. Trying out a more functional approach to Javascript.
Would be nice to pull the regex in to a variable to make it more readable but not sure how to do this?

https://repl.it/HeEg/3

18

function reverseWord (word) {
return word.split(’ ‘).reverse().join(’ ');
}

I’ll tackle the trickier ones tomorrow.

19

My solution in JavaScript:

  1. Create a new array (newStr) that contains only the words of the string in reverse - using a regex to remove the punctuation (non-word characters that are not white-space);
  2. Convert str into an array of words and punctuation only - using a regex to to prepare the punctuation for the split by adding a space before;
  3. Iterate over the str array to look for items that are punctuation - testing each item using .test() with a regex to test for non-word characters;
  4. If punctuation is found in the str array then use indexOf() and splice() to add the punctuation item to the correct index position in the newStr array;
  5. Finally join the newStr array and remove any spaces that come before punctuation (which were added by the join).
function reverseStr(str) {
	newStr = str.replace(/([^\w\s])/gi, '').split(' ').reverse();
	str = str.replace(/([^\w\s])/gi, " " + '$1').split(' ');
	for (var i in str) {
		if ((/\W/).test(str[i])) {
			var index = str.indexOf(str[i]);
			newStr.splice(index, 0, str[i]);
		}
	}
	return newStr.join(' ').replace(/\s(\W)/gi, '$1');
}
20

function reverse(str) {
var words = str.split(" ");
var newStr = words[words.length - 1];
for (var i=words.length - 2; i>=0; i–) {
newStr += " "+words[i];
}
return newStr;
};

21

https://repl.it/He07/0

22

Algorithm

I decided to first split the string on spaces, giving me an array of words including punctuation. I then loop through half the length of the array to swap words at corresponding distances from the edges of the array (last becomes first and vice versa, etc.)

The swap is done by splitting the two words into “punctuation-words” which are one or more non-alphanumeric characters and regular alphanumeric words. I then use a regular expression to find the index of the alphanumeric word (assumes there’s only one per entry) and swap it with the alphanumeric word in the other end. I then put these pieces two pieces back into the large array where they now have their words swapped, but punctuation is intact.

To make it easier to match alphanumeric words, I assigned a callback function to a variable used for find (word, row 2).

Space Complexity

I do use the array of split words rather than the actual string, not sure what we count as in-place in this case. I could modify the string directly, but string operations are expensive and more complicated than working with an array. My goal was to avoid needing an auxiliary array, which I did.

Inside the for loop at least a temporary variable to store one of the values we’re swapping is required. For readability purposes I’ve declared some additional variables in here.
On a larger scale what I store inside the for loop becomes less important though, especially if the input string becomes larger (which is when complexity becomes relevant).

Time Complexity

  1. Split string, I assume O(n) in javascript, where n is length of string
  2. For-loop running m/2 iterations, where m is length of array
    2.1. 2xSplit string, O(w) where w is length of word
    2.2. 4xFind, (little more than) O(w) where w is length of word

Read and write to array are constant time operations, so leaving those out of the list. The part I’m not sure about is joins. Given the immutability of strings the time complexity could be closer to O(n^2). Not counting the join we get n + m*(6w)/2 = n + 3m*w ~ n + 3n = 4n, so O(n). Depending on how join works we’ll end up somewhere between O(n) and O(n^2).

https://repl.it/HeUe/2

2 Likes
23

This was fun to play with! I have solved it a couple of different ways, including the intermediate difficulty level to handle punctuation, and while I was at it, I also wrote methods to keep the capitalization of the earlier sentence. I also provide a method that only moves punctuation, since that’s what the intermediate difficulty challenge asks for.

https://repl.it/HeMo/5

1 Like