How would you improve this algorithm? (c string re

Question

Working through some programming interview challenges I found online, I had to write an algorithm to reverse a const char * and return a pointer to a new char *. I think I have it, but to make it work properly I had to do some wonky stuff - basically having to account for the null-terminating character myself. Somehow I feel this is wrong, but I'm stumped, and I was wondering if someone could help me out:

char * reverse(const char * str)
{
  int length = strlen(str);
  char * reversed_string = new char[length+1];

  for(int i = 0; i < length; ++i)
  {
    reversed_string[i] = str[(length-1) - i];
  }
  //need to null terminate the string
  reversed_string[length] = '\0';

  return reversed_string;

}

int main(int argc, char * argv[])
{

  char * rev_str = reverse("Testing");

  cout << "Your string reversed is this: " << rev_str << endl;

  delete rev_str;
  rev_str = 0;

  return 0;
}

Answer 1

std::reverse from <algorithm> works for strings and char arrays:

string str = "Hello";
char chx[] = "Hello";

reverse(str.begin(), str.end());
reverse(chx, chx + strlen(chx));

cout << str << endl;
cout << chx << endl;

/EDIT: This, of course, modifies the original string. But STL to the rescue. The following creates a new reversed string. Unfortunately (?), this doesn't work directly on C char arrays without creating an additional (implicit) copy:

string reverse_string(string const& old) {
    return string(old.rbegin(), old.rend());
}

cout << reverse_string("Hello") << endl;

Answer 2

We've used this question before -- with the surprisingly results of finding a lot of people that can't do it (even with significant C/C++ experience!). I prefer the in-place variant since it saves some overhead, and has the added twist of only needing to iterate over strlen(s)/2 characters.

Your solution in an interview would be fine. A (correct!) solution using pointer instead of array syntax would rate a bit higher since it shows a greater comfort level with pointers which are so critical in C/C++ programming.

The minor critiques would be to point out that strlen returns a size_t not an int, and you should use delete [] on rev_str.

Answer 3

A method that doesn't need temporary variables

int length = strlen(string);
for(int i = 0; i < length/2; i++) {
  string[i] ^= string[length - i] ^= string[i] ^= string[length - i];
}

Answer 4

It wouldn't be more efficient, but you could demonstrate knowledge of data structures by doing something like pushing each letter onto a stack, and then popping them off into your newly allocated buffer.

It would take two passes and a scratch stack, but I would probably trust myself more to get this right the first time then to not make an off-by one error like the above.

char* stringReverse(const char* sInput)
{
    std::size_t nLen = strlen(sInput);
    std::stack<char> charStack;
    for(std::size_t i = 0; i < nLen; ++i)
    {
        charStack.push(sInput[i]);
    }
    char * result = new char[nLen + 1];
    std::size_t counter = 0;
    while (!charStack.empty())
    {
        result[counter++] = charStack.top();
        charStack.pop();
    }
    result[counter] = '\0';
    return result;
}

Answer 5

When asking this question as an interviewer, I am looking to a clean, understandable solution and may ask how the initial solution could be made more efficient. I'm not interested in 'smart' solutions.

I am thinking about thing like; has the candidate made the old with off by one error in their loop, do they pre-allocate enough memory, do they check to bad input, do they use sufficiently efficient types.

Unfortunately, as already pointed out, too many people can't even do this.

Answer 6

If I was doing the interviewing I would be a bit more fussy with the quality of the solution in terms of its robustness, not just it's performance.

All of the answers submitted thus far will fail if passed a null pointer - most of them leap to immediately calling strlen() on a possible null pointer - which will probably segfault your process.

Many of the answers are obsessive about performance to the point that they miss one of the key issues of the question: reverse a const char *, i.e. you need to make a reversed copy, not reverse in-place. You'll find it difficult to halve the number of iterations if a copy is required!

This is an interview question, so we want to look at the details of the algorithm, but in the real world this just highlights the value of using standard libraries whenever possible.