Background

Gone are the days when Software companies used to ask questions like - write a function to reverse a given string. With increasing number of websites like this, providing solution to every other question asked in interviews, Companies are always going on step ahead in phrasing their questions to the candidate facing the interview. This one is a nice example of the same and was asked by Google from one of my friend.

Problem Definition

Based on given problem, Think of an example first to understand question better.
If You are given an input string
:


"Code Boat provides best programming interview material."


Your program should generate and output like
  
"material. interview programming best provides Boat Code"


Solution 1:

Hmmm... Honestly, I believe in code reusablility. I just started thinking about strrev() function that used to asked in interviews previously, Yes!! you guessed it right it reverses whole string. But Didn't I say in the beginning that Companies have upgraded this question?? Yes, but keep in mind that this is a little bit different than what they used to ask previously. How?
  • If I reverse whole string in Step 1.
  • Then If I keep reversing all the words in it, one by one. I get an answer?
In case, you couldn't follow let us say we have small string "it is" so here is what we do:
  • Reverse Whole String it - "si it"
  • Now Reverse words one by one first "si" to "is" and then "ti" to "it" and you get "is it"
So this all boils down to writing one function with following definition:

 
void reverseString(char* string, int startIndex, int endIndex);


And then invoking it twice
  • first with startIndex - 0 and endIndex- index of last char in whole string.
  • Then by calling this function by passing start index and end index of individual words.

  #include<stdio.h>
#include<stdlib.h>
#include<string.h>

void reverseString(char str[], int startIndex, int endIndex)
{
char temp;
int i, j;

while(endIndex > startIndex)
{
temp = str[startIndex];
str[startIndex] = str[endIndex];
str[endIndex] = temp;
startIndex++;
endIndex--;
}
}

int main()
{
char str[] = "Code Boat provides best programming interview material.";
int length, index = 0, start=0, end;
length = strlen(str)-1;

//Reverse whole string first
reverseString(str,0,length);
printf("%-15s: %s\n","First Reversal",str);

//Reverse every word now
do
{
if(str[index] == ' ' || str[index]=='\0')
{
end = index-1;
reverseString(str,start,end);
start = index+1;
}
}while(index++ <= length);

printf("%-15s: %s\n","Final Reversal",str);
system("pause");
}



OUTPUT:

First Reversal : .lairetam weivretni gnimmargorp tseb sedivorp taoB edoC
Final Reversal : material. interview programming best provides Boat Code


Solution 2:

In case you are not asked to do an in-place reversal. Meaning, you can use extra space as well then you can use STACK data structure to PUSH all the words in given string and then POP them out to get reverse of string. Because STACK has a property Last In First Out. So output string contains the last word first. This solution is easy to code if you are using C# or JAVA like languages.

  
Algorithm For Solution 2

Input: "Code Boat provides best programming interview material."

//Pushing data onto stack
1. Read first word "Code" from string and PUSH on stack.
2. Read next word "Boat" and PUSH onto stack.
3. Repeat above steps until all words are exhausted.

//Solution Array
4. Declare index = 0 as start point.
5. POP first word i.e. material from stack and insert in str[index]
upto its str[index+lengthOfWord].
6. POP second word i.e. interview and insert in array


3 comments

  1. Ashish // September 29, 2008 at 5:26 PM  

    This is a great solution . but I am still confuse after string reversal how you are going to reverse each words in string using same stack ? Or you are going to use one more stack.

  2. CodeBoat // September 29, 2008 at 11:54 PM  

    Ashish,
    My sincere apologies for leaving a scope of confusion. I've included the complete code for solution 1. Although, I preferred to provide only algorithm for the second one so that you can think about it yourself. Thanks for reading!!

  3. Nitin Anand // October 1, 2008 at 12:11 PM  

    Gud solution sandy..!!
    logic is simple
    1. reverse whole sentence
    2. reverse each word
    done...!! :)