Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

# Reverse The Ordering Of Words In a String Problem

Given a string s containing a set of words, transform it such that the words appear in the reverse order. Words in s are separated by one or more spaces.

##### Example One

Input: “I will do it.”

Output: “it. do will I”

##### Example Two

Input: "   word1  word2 " (Note: there are 3 spaces in the beginning, 2 spaces between the words and 1 space at the end.)

Output: " word2  word1   " (Note: there is 1 space in the beginning, 2 spaces between the words and 3 spaces at the end.)

##### Example Three

Input: "word1, word2;"

Output: "word2; word1,"

##### Notes

Input Parameters: Function one argument, string s.

output: Return a string with the answer.

##### Constraints:

● 1

● s contains only lowercase and uppercase alphabetical characters, spaces and punctuation marks ".,?!':;-" (quotes not included).

Punctuation marks are considered a part of the word.

Usage of built-in string functions is NOT allowed.

An in-place linear solution is expected.

For languages that have immutable strings, convert the input string into a character array and work in-place on that array. Convert it back to the string before returning. Ignore the extra linear space used in that conversion, as long as you're only using constant space after conversion to character array.

Trivia: This is a very old interview question. Google used it as one of their qualifier questions in Google CodeJam in the past, too.

#### Solutions

One idea for the solution is:

1) Reverse the whole string.

2) Then reverse the individual words.

For example, if the input is:

s = "Have a nice day!"

1) Then first reverse the whole string,

s = "!yad ecin a evaH"

2) Then reverse the individual words,

s = "day! nice a Have"

##### Time Complexity:

O(n).

The first pass over the string is obviously O(n/2) = O(n). The second pass is O(n + combined length of all words / 2) = O(n + n/2) = O(n), which makes this an O(n) algorithm.

O(1).

##### Space Complexity:

O(n).

``````
// -------- START --------

/*
Suppose s = "abcdefgh" and we call reverse_string(s[2], 4) then this function will reverse "cdef"
part of "abcdefgh".
*/
void reverse_string(char *str, int len)
{
for(int i = 0; i < len / 2; i++)
{
swap(str[i], str[len - 1 - i]);
}
}

string reverse_ordering_of_words(string s)
{
int len = s.length();
// Reverse whole string.
reverse_string(&s[0], len);
int word_beginning = 0;
// Find word boundaries and reverse word by word.
for(int word_end = 0; word_end < len; word_end++)
{
if(s[word_end] == ' ')
{
reverse_string(&s[word_beginning] , word_end - word_beginning);
word_beginning = word_end + 1;
}
}
/*
If there is no space at the end then last word will not be reversed in the above for loop.
So need to reverse it.
Reverse the last word.
*/
reverse_string(&s[word_beginning], len - word_beginning);
return s;
}

// -------- END --------
``````

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# Reverse The Ordering Of Words In a String Problem

Given a string s containing a set of words, transform it such that the words appear in the reverse order. Words in s are separated by one or more spaces.

##### Example One

Input: “I will do it.”

Output: “it. do will I”

##### Example Two

Input: "   word1  word2 " (Note: there are 3 spaces in the beginning, 2 spaces between the words and 1 space at the end.)

Output: " word2  word1   " (Note: there is 1 space in the beginning, 2 spaces between the words and 3 spaces at the end.)

##### Example Three

Input: "word1, word2;"

Output: "word2; word1,"

##### Notes

Input Parameters: Function one argument, string s.

output: Return a string with the answer.

##### Constraints:

● 1

● s contains only lowercase and uppercase alphabetical characters, spaces and punctuation marks ".,?!':;-" (quotes not included).

Punctuation marks are considered a part of the word.

Usage of built-in string functions is NOT allowed.

An in-place linear solution is expected.

For languages that have immutable strings, convert the input string into a character array and work in-place on that array. Convert it back to the string before returning. Ignore the extra linear space used in that conversion, as long as you're only using constant space after conversion to character array.

Trivia: This is a very old interview question. Google used it as one of their qualifier questions in Google CodeJam in the past, too.

#### Solutions

One idea for the solution is:

1) Reverse the whole string.

2) Then reverse the individual words.

For example, if the input is:

s = "Have a nice day!"

1) Then first reverse the whole string,

s = "!yad ecin a evaH"

2) Then reverse the individual words,

s = "day! nice a Have"

##### Time Complexity:

O(n).

The first pass over the string is obviously O(n/2) = O(n). The second pass is O(n + combined length of all words / 2) = O(n + n/2) = O(n), which makes this an O(n) algorithm.

O(1).

##### Space Complexity:

O(n).

``````
// -------- START --------

/*
Suppose s = "abcdefgh" and we call reverse_string(s[2], 4) then this function will reverse "cdef"
part of "abcdefgh".
*/
void reverse_string(char *str, int len)
{
for(int i = 0; i < len / 2; i++)
{
swap(str[i], str[len - 1 - i]);
}
}

string reverse_ordering_of_words(string s)
{
int len = s.length();
// Reverse whole string.
reverse_string(&s[0], len);
int word_beginning = 0;
// Find word boundaries and reverse word by word.
for(int word_end = 0; word_end < len; word_end++)
{
if(s[word_end] == ' ')
{
reverse_string(&s[word_beginning] , word_end - word_beginning);
word_beginning = word_end + 1;
}
}
/*
If there is no space at the end then last word will not be reversed in the above for loop.
So need to reverse it.
Reverse the last word.
*/
reverse_string(&s[word_beginning], len - word_beginning);
return s;
}

// -------- END --------
``````

## Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Hosted By
Ryan Valles
Founder, Interview Kickstart
Accelerate your Interview prep with Tier-1 tech instructors
360° courses that have helped 14,000+ tech professionals
100% money-back guarantee*