This is a solution to problem 3 on the hard interview questions node. If you have not read the question, the following will make no sense to you:

First, reverse the whole string (by swapping the first and the last character, towards the middle, etc). This should be enough of a hint to get you started. If not, read on:

Then reverse the order of the characters in each word. Now the characters in each word are in the original order (they were reversed twice overall), but the words are in reverse order (the first word is now at the end, etc.)

/*
* =====================================================================================
*
* Filename: rev_word.cpp
*
* Description: Given an array of characters which form a sentence of words,
* give an efficient algorithm to reverse the order of the words
* (not characters) in it.
*
* Version: 1.0
* Created: Sunday 28 February 2010 08:34:21 IST
* Revision: none
* Compiler: g++
*
* Author: vikram singh parihar, vikram2rhyme@gmail.com
* College: National Institute of Technology, Raipur, CG, India
*
* =====================================================================================
*/

#include
#include
using namespace std;
void rev_word(char*, int);

// === FUNCTION ======================================================================
// Name: main
// Description: main function
// =====================================================================================
int
main ( int argc, char** argv )
{
char str = "vikram singh parihar computer science & engineering nit raipur";
rev_word(str, sizeof str - 1);
cout < "The reversed word string is:\n" < str < endl;
return EXIT_SUCCESS;
} // ---------- end of function main ----------

/*
* === FUNCTION ======================================================================
* Name: rev_word
* Description: Reverses the order of the words in a string. First reverse entire
* string character by character and then reverse each word independently
* character by character.
* =====================================================================================
*/
void
rev_word ( char* str, int len )
{
for (int i = 0; i < len / 2; ++i) {
char temp = str i;
str i = str len - i - 1;
str len - i - 1 = temp;
}

int p = 0, l = 0;
while (true) {
while (str p + l != ' ' && str p + l != '\0') ++l;
for (int i = p; i < p + l / 2; ++i) {
char temp = str i;
str i = str 2*p + l - i - 1;
str 2*p + l - i - 1 = temp;
}
p += l;
while (str p == ' ') ++p;
if (str p == '\0') break;
l = 0;
}
} /* ----- end of function rev_word ----- */

Log in or register to write something here or to contact authors.