Interview Challenge (Word Reversal)

[Narue]

Let's pretend that I'm interviewing you for a C++ job. I want to know how you[1] approach problems and the extent of your C++ prowess, so I'm going to ask you to solve short problems in C++[2]. These problems range from beginner to advanced, and may be more than they seem. Good luck!

[1] "You" being collective. Everyone is welcome to put their heads together and/or build on the questions or solutions of everyone else. In fact, I encourage it.

[2] Each problem will have a separate thread, to keep things on-topic. If it turns out that this is a fun game, I'll post new problems regularly.

Okay then, here we go:

Problem: Write some code that reverses words.

[iamthwee]

Let's pretend you actually have some real work to do :)

[Narue]

Let's pretend that I'll heavily moderate this thread to keep it on-topic.

[iamthwee]

Are you also pretending you are a c++ employer? Cos all this presence is confusing me.

[edit]Sorry I'm being really stupid, ignore me[/edit]

[Killer_Typo]

because i happen to think you are one of the brighter minds i have met in a while i will take you up on your challenges. i will post back shortly with some code :-D

[Bench]

Problem: Write some code that reverses words.

My first thought which springs to mind, is, how would you define a 'word'?

is it..A sequence of alphanumeric characters
A sequence of alphanumeric characters & punctuation
A sequence of purely Alphabetical characters
Assuming any particular character set (ASCII, Unicode, etc)

My next thought... what do you mean by "reverses words"Reverses the order of a list of "words" (assuming "word" is defined)
Reversing the order a set of characters appear in a word
A combination of the above (Which would be more like reversing a 'sentence')

Those questions aside, here's how i'd do it in C++ (Making assumptions about the above, of course :) )

#include <iostream>
#include <ostream>
#include <string>
#include <sstream>
#include <deque>
#include <algorithm>
#include <functional>

class reverse_word : public std::unary_function<std::string, std::string>
{
public:
    std::string& operator()(std::string& str)
    {
        std::reverse(str.begin(), str.end());
        return str;
    }
};

int main()
{
    std::string str ("the quick brown fox jumps over the lazy dog");
    std::cout << str << std::endl;

    std::stringstream ss (str);
    typedef std::deque<std::string> list_t;
    list_t word_list;
    std::string temp;
    while( ss >> temp )
        word_list.push_back(temp);
    std::for_each(word_list.begin(), word_list.end(), reverse_word() );
    list_t::const_iterator i;
    for( i = word_list.begin() ; i != word_list.end() ; ++i )
        std::cout << *i << " ";
}

[Narue]

>My first thought which springs to mind, is, how would you define a 'word'?
That's an excellent reaction. After a moment's thought, I'm thinking we (the imaginary company you're interviewing for) could use something like this to process subroutine parameters in a compiler while building a stack frame. The parameters are evaluated from last to first, but written first to last. So for our needs a word is a valid identifier (our compiler uses the same identifier rules as C++).

>My next thought... what do you mean by "reverses words"
Another good question. We'll be using the parameter identifiers themselves as keys into a map for the symbol table, so it's probably not a good idea to modify the source strings. So in our case, the list [arg1, arg2, arg3] would be reversed into [arg3, arg2, arg1] .

>Those questions aside, here's how i'd do it in C++
I like it. But I forgot to tell you that our development environment is extremely buggy and resource intensive (management is looking into replacing it). Using the standard library would be a bad idea for this component since it'll be used very often during a compilation phase.

[Killer_Typo]

simple and it works :)

#include "stdafx.h"
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;
void reverseword(char * reverse) {
    size_t size = strlen(reverse);              //get the size of the char *
    for(size_t i = 1; i <= size; i++)     
    {
        cout << reverse[size - i];                  //output the word
    }
}
void reverseword (string reverse) {
    size_t size = reverse.size();
    string::reverse_iterator walkword;
    for(walkword = reverse.rbegin(); walkword < reverse.rend(); walkword++)
    {
        cout << *walkword;
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    cout << "Method one for string reversal" << endl;
    cout << "==============================" << endl;
    cout << "== Using Char * and cin.getline" << endl;
    cout << "== using for statement to itterate" << endl;
    cout << "==============================" << endl;
 
    char * getwords = new char();       //will hold the words
    cout << "Please enter the words to reverse" << endl << endl << endl;
    cin.getline(getwords,100);           //get the word(s) to reverse
    reverseword(getwords);      //reverse the words
    cin.sync();//clean up buffer for next example
 
    cout << endl << endl << endl;
    cout << "Method Two for string reversal" << endl;
    cout << "==============================" << endl;
    cout << "== Using std::basic_string cin.getline" << endl;
    cout << "== using build in itterator members" << endl;
    cout << "==============================" << endl;
 
    string getwordsagain;
    cout << "Please enter the words to reverse" << endl << endl << endl;
    getline(cin, getwordsagain);
    reverseword(getwordsagain);
    cin.sync();                 //clean the buffah
    return 0;
}

i know of a few things i could do to optimize but for the question it works...or so i believe :P

[Narue]

>simple and it works
Your code exhibits undefined and implementation-defined behavior (start a new thread asking why if you want details). It also alters the words, which won't work for us, we need the words to be reversed without also reversing the characters in each word. But it's a start.

[Killer_Typo]

>simple and it works Your code exhibits undefined and implementation-defined behavior (start a new thread asking why if you want details). It also alters the words, which won't work for us, we need the words to be reversed without also reversing the characters in each word. But it's a start.

cool i started a new thread.

so from what i am gathering if i were to input the string

hello world

you dont want

dlrow olleh

you want

olleh dlrow

the words reversed but their location is intact?

:)

i figure i should ask questions now rather than later :P

[Narue]

>the words reversed but their location is intact?
The other way around. "hello world" would become "world hello".

[Killer_Typo]

>the words reversed but their location is intact? The other way around. "hello world" would become "world hello".

oohhhh awesome. cool i will work on that then.

quick question though.

would you consider the ' ' to be the delimeter for a word; furthermore, what about hyphinated words. words broken apart by hyphens or a string of words connected by them. are they to be considered as one whole word or should they be split in the process.

[Narue]

>would you consider the ' ' to be the delimeter for a word
A delimiter, yes. Check my replies to Bench for tips on how to define a word for this problem.

[hinduengg]

this is my code but you would need to change the headers as per new rules of C++

#include<iostream.h>
#include<conio.h>
#include<string.h>
#include<stdio.h>
int main()
{
  char a[100];
char b[100];
cout<<"enter sentence"<<endl;
cin.getline(a,100);
strcpy(b,' ');
strcat(b,a);
strcpy(a,b);
int x,y,len,k;
len=strlen(a);
k=len;
for(x=len-1;x>=0;x--)
{
  if(a[x]==' ')
   { 
      for(y=x+1;y<=k;y++)
        cout<<a[y];
           k=x;
    }
  }
return 0;
}

if input is -I AM BEST
OUTPUT IS-BEST AM I

[Lerner]

Goal: Reverse words in a sentence without destroying sentence and without using STL.

Assumptions:
1) Input sentence not longer than 6400 char
2) Less than 81 words per sentence
3) Each word less than 81 char long
4) Output is a sentence with words reversed

#include <iostream>
#include <cstring>

int main()
{
  char sentence[6401];
  char target[6401];
  char words[80][81];
  char reversed[6401];
  char * word;
  int len;
  int index = 0;

  //get a non empty sentence
  do
  {
     std::cout << "enter a string of words" << std::endl;
     std::cin.getline(sentence, 6400);
     len = strlen(sentence);
   }while(len < 1);

  //parse target, keep sentence intact
  strcpy(target, sentence);

  //get first word in target
  word = strtok( target, " " );

  // While there are words left in target
  while( word != NULL )
  {
    //put word in words
    strcpy(words[index++], word);
    
    // Get next word
    word = strtok( NULL, " ");
  }

  strcpy(reversed, words[index - 1]);
  for(int k = index - 2; k >= 0; k--)
  {
    strcat(reversed, " " );
    strcat(reversed, words[k]);
  }
 
  std::cout << "the original sentence was: " << sentence << std::endl << std::endl;

  std::cout << "the sentence with words in reverse order: " << reversed << std::endl;

  std::cin.get();
  return 0;
}

Weakness---assumptions may not be appropriate

Strength---avoids need to create user defined container to hold words parsed from input before reversal is accomplished.

[Lerner]

VERSION 2:
Uses istringstream to parse input sentence rather than strtok(), the use of which isn't straightforward and some people don't like.

#include <iostream>
#include <cstring>
#include <sstream>

int main()
{
  char sentence[6401] = "";
  char words[80][81];
  char reversed[6401];
  int len;
  int index = 0;

  do
  {
    std::cout << "enter a string of words" << std::endl;
    std::cin.getline(sentence, 6400);
    len = strlen(sentence);
  }while(len < 1);

  //load istringstream
  std::istringstream ss (sentence);
  
  //load words by parsing input using space as the delimeter
  while(ss >> words[index])
    ++index;

  //reverse words
  strcpy(reversed, words[index - 1]);
  for(int k = index - 2; k >= 0; k--)
  {
    strcat(reversed, " " );
    strcat(reversed, words[k]);
  }

  std::cout << "original sentence was: " << sentence << std::endl;

  std::cout << "reversed sentence is: " << reversed << std::endl;

  std::cin.get();
  return 0;
}

[Killer_Typo]

Goal: Reverse words in a sentence without destroying sentence and without using STL. Assumptions: 1) Input sentence not longer than 6400 char 2) Less than 81 words per sentence 3) Each word less than 81 char long 4) Output is a sentence with words reversed Weakness---assumptions may not be appropriate Strength---avoids need to create user defined container to hold words parsed from input before reversal is accomplished.

i had read online that strtok may not be safe and the better version to use is strtoke_s

after messing around with strtok_s for a bit i found that this version was a bit more easy to use.

[Lerner]

VERSION 3:
stringstreams (from sstream header) apparently are for STL strings, so use strstreams (from strstream header) for both parsing and reversing

#include <iostream>
#include <strstream>

int main()
{
  char sentence[6401] = "";
  char reversed[6401];
  char words[80][81];
  int len;
  int index = 0;

  do
  {
    std::cout << "enter a string of words" << std::endl;
    std::cin.getline(sentence, 6400);
    len = strlen(sentence);
  }while(len < 1);

  std::istrstream ss (sentence);
  
  //load words
  while(ss >> words[index])
    ++index;

  //reverse words in sentence
  std::ostrstream oss(reversed, sizeof(reversed));
  oss << words[index -1];

  for(int i = index - 2; i >= 0; --i)
  {
    oss << " ";
    oss << words[i];
  }

  /* null terminate oss, apparently not all compiler implentations do this automatically and it really did a number on my noggin 'til I found a reference pointing this out */

  oss << std::ends;

  std::cout << "original sentence was: " << sentence << std::endl;

  std::cout << "reversed sentence is: " << reversed << std::endl;

  std::cin.get();
  return 0;
}

[iamthwee]

When compiling Lerner's version 3 on linux (g++) :-

/usr/include/c++/4.1.2/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header. Please consider using one of the 32 headers found in section 17.4.1.2 of the C++ standard. Examples include substituting the <X> header for the <X.h> header for C++ includes, or <iostream> instead of the deprecated header <iostream.h>. To disable this warning use -Wno-deprecated.

> after messing around with strtok_s for a bit i found that this version was a bit more easy to use.

is strtok_s standard c++ then?

[Killer_Typo]

> after messing around with strtok_s for a bit i found that this version was a bit more easy to use. is strtok_s standard c++ then?

no concern of mine, do some searching around online and you will find a great wealth of information on both strtok and strtok_s

cheers.