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.

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.

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;
}

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.

[Bench]

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] .

In which case, i'll make the assumption that the input is going to look like [arg1, arg2, arg3] - and that this input needs to stay as-is.

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.

Wouldn't it be better, then, to write it as a 'C' program? :)

Assuming, at the least, the C standard library is available (By my reckoning, any function from the C standard library is probably going to be at least as efficient for a task as any other)

#ifndef ID_LIST_H
#define ID_LIST_H

#include <cstring>

class identifier_list
{
    char* params;
    const size_t size;
    const char delimiter;
    static char* strip_symbols(char* const);
    static char* validate_tokens(char* const);
    static char* reverse_order(char* const, size_t, char);
public:
    identifier_list(const char args_in[], char delim) : delimiter(delim), size( strlen(args_in) + 1 )
    {
        params = new char[size];
        strcpy(params, args_in);

        params = strip_symbols(params);
        if ( !( params = validate_tokens(params) ) )
            throw("Invalid Identifier List\n");
        params = reverse_order(params, size, delim);
    }

    const char* get();     

    ~identifier_list()
    {
        delete[] params;
    }
};

#endif

#include <cstring>
#include "id_list.h"

const char* identifier_list::get()
{
    return params;
}

char* identifier_list::strip_symbols(char* str)
{
    static char* const symbols("[,]");
    static const char whitespace(' ');
    char* iter(str);
    while(*iter)
    {
        if( strchr( symbols, *iter ) )
            *iter = whitespace;
        ++iter;
    }
    return str;
}

char* identifier_list::validate_tokens(char* const str)
{
    static const char* const valid(" abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890_");
    char* iter(str);
    while(*iter)
    {
        if( ! strchr(valid, *iter) )
            return NULL;
        ++iter;
    }
    return str;
}

char* identifier_list::reverse_order(char * const in, size_t size, const char separator)
{
    char* const out = new char[size];
    char* out_last = out;
    while( *in )
    {
        char* word_begin = strrchr(in, separator);
        if( !word_begin )
            word_begin = in;

        out_last = strcpy(out_last, word_begin);
        out_last += strlen(out_last);
        *word_begin = '\0';
    }
    strcpy(in, out);
    delete[] out;
    return in;
}

#include <iostream>
#include "id_list.h"

int main()
{
    char arg_list[]("[argument1, arg2, a_very_long_argument_for_number_3, arg4]");
    try
    {
        identifier_list il (arg_list, ' ');
        std::cout << il.get() << '\n';
    }
    catch(const char* error)
    {
        std::cout << error;
    }
}

[Rashakil Fol]

>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++).

WHAT??? That's an asinine way of doing things.

[Narue]

>That's an asinine way of doing things.
Taken out of context, yes. You can't be sure without the whole story.

>In which case, i'll make the assumption that the input is going to
>look like [arg1, arg2, arg3] - and that this input needs to stay as-is.
That was merely my own notation. arg1, arg2, and arg3 will actually come individually through a tokenizer stream. For the purposes of this problem you can assume that reading the tokens can be done like so without any problems and the Token type is equivalent to a string:

Token tok;

while ( tokenizer>> tok ) {
  // TODO: Add the token to the stack frame
}

In fact, you can assume that the tokens you receive have already been checked for validity.

However, because the tokens come in the wrong order, we can't directly add each token to the stack frame. They need to be reversed first. We would like something elegant (ie. simple yet efficient) that doesn't use up too much extra storage.

>Wouldn't it be better, then, to write it as a 'C' program?
If you'd like to, you can use C. But make sure that it won't choke a C++ compiler.

[Bench]

ah ok.. Based on that, here's my third attempt :icon_smile:

#include <iostream>
#include <string>

class tokenstream
{
public:
    typedef std::string token_type;

    tokenstream(const char args_in[], char delim) : delimiter(delim), 
        tokens(args_in), fail(false) {}

    tokenstream& operator >> (token_type&);
    operator bool () const { return !fail; }
    operator = ( token_type );
    operator = ( const char* );
    void clear() { fail = false; }
private:
    bool fail;
    token_type tokens;
    const char delimiter;
};

tokenstream& tokenstream::operator >> (token_type& tok_out)
{
    if( tokens.empty() )
    {
        fail = true;
        return *this;
    }

    size_t pos = tokens.rfind(delimiter);
    if( pos != token_type::npos )
        tok_out = tokens.substr(pos+1);
    else
    {
        pos = 0;
        tok_out = tokens.substr(pos);
    }
    
    tokens.erase(pos);
    return *this;
}
   
tokenstream::operator = ( token_type str )
{
    tokens = str;
    return *this;
}

tokenstream::operator = ( const char* str )
{
    tokens = str;
    return *this;
}

int main()
{
    const char* arg_list("arg1 argument2 very_long_argument_number_3 argument_4");
    tokenstream tokenizer(arg_list, ' ');
    tokenstream::token_type tok;
    while( tokenizer >> tok )
        std::cout << tok << ' ';
    std::cout << "\n\n";

    tokenizer.clear();

    char more_args[]("sheep cow horse chicken");
    tokenizer = more_args;
    while( tokenizer >> tok )
        std::cout << tok << ' ';
    std::cout << "\n\n";
}

I can see that I should have asked more questions about how the code was going to be used.. :icon_smile:

[~s.o.s~]

Narue, before starting a new thing you must finish off pending business. We are still waiting for the results of the previous competition...

[hinduengg]

Is it a monthly competition , if so what does the winner receive ?
I did not read about this in the FAQ. Is this type of competition an integral part of Daniweb?

:) Please tell,
hinduengg

[Narue]

>We are still waiting for the results of the previous competition...
Which one was that?

[~s.o.s~]

> Which one was that?
This?

[Narue]

>Based on that, here's my third attempt
Close, but you're still treating the arguments as one whole string. You only get them one at a time. For example:

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{
  typedef string Token;
  
  istringstream tokenizer ( "arg1 arg2 arg3" );
  Token tok;

  while ( tokenizer>> tok ) {
    // TODO: Add the token to the stack frame
  }
}

You're welcome to modify the loop, but the tokenizer is an integral piece of the compiler, so we can't rewrite it to give you all of the arguments as a single string.

[Narue]

>> Which one was that?
>This?
I could have sworn that one fizzled out. Oh well.