How would you improve this algorithm? (c string reversal)

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

I had this question once. That's the first answer that comes to mind, but the follow-up is, "now do it without allocating any memory."

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

EDIT: Some folks have expressed disdain for not using pointers. This is a tiny bit more readable, though not completely optimal. Others have entered the pointer solution, so I won't repeat it here.

One commenter challenged that it should be doable without a (stack based) holding cell for the swap. The mechanism for doing that is bitwise XOR. Replace the inside of the loop with

string[i] = string[i] ^ string[length - i];
string[length - i] = string[i] ^ string[length - i];
string[i] = string[i] ^ string[length - i];

But in general, modern compilers can optimize out the local variable of a naive swap. For details, See Wikipedia

Answer 2

this works nicely:

#include <algorithm>
#include <iostream>
#include <cstring>

void reverse_string(char *str) {    
    char *end = str + strlen(str) - 1;
    while (str < end) {
     std::iter_swap(str++, end--);
    }
}

int main() {
    char s[] = "this is a test";
    reverse_string(s);
    std::cout << "[" << s << "]" << std::endl;
}

Answer 3

if( string[0] )
{
    char *end = string + strlen(string)-1;
    while( start < end )
    {
        char temp = *string;
        *string++ = *end;
        *end-- = temp;
    }
}

Answer 4

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 5

I would have solved it sort of like this (my c is a bit rusty though, forgive me)

char *reverse( const char *source ) {
  int len = strlen( source );
  char *dest = new char[ len + 1 ];
  int i = 0;
  int j = len;
  while( j > 0 ) {
    dest[j--] = src[i++];
  }
  dest[i] = \0;
  return dest;
}

Answer 6

Actually, given the constraint that the original string be left unmodified, I think the original approach given in the question is the best. All these fancy approaches to reversing in place people are posting are great, but once copying the given string is factored in, they are all less efficient than simply copying the string backwards.

Answer 7

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 8

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 9

Uh? No one did it with pointers?

char *reverse(const char *s) {
    size_t n = strlen(s);
    char *dest = new char[n + 1];
    char *d = (dest + n - 1);

    dest[n] = 0;
    while (*s) {
        *d-- = *s++
    }

    return dest;
}

Hopefully years of Java haven't ruined my C ;-)

Edit: replaced all those strlen calls with an extra var. What does strlen return these days? (Thanks plinth).

Answer 10

Your code is straight forward and unsurprising. A few things:

1. Use size_t instead of int for your loop index
2. While your compiler is most likely smart enough to figure out that (length -1) is invariant, it's probably not smart enough to figure out that (length-1)-i is best replaced by a different loop variable that is decremented in each pass
3. I'd use pointers instead of array syntax - it will look cleaner to me to have *dst-- = *src++; in the loop.

In other words:

char *dst = reversed_string + length;
*dst-- = '\0';
while (*src) {
   *dst-- = *src++;
}

Answer 11

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 12

@Konrad Rudolph: (sorry I don't have the "experience" to post a comment)

I want to point out that the STL supplies a reverse_copy() algorithm, similar to reverse(). You need not introduce a temporary the way you did, just allocate a new char * of the right size.

Answer 13

WRT: "Now do it without temporary holding variable"... Something like this perhaps (and keeping array indexing for now):

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

Answer 14

I know this is highly unportable but x86 assembler instruction bswap lets you swap four bytes by means of just one instruction which can be a good path to boost the code.

This is an example of how to get it working with GCC.

/* 
 * reverse.c
 *
 * $20081020 23:33 fernando DOT miguelez AT gmail DOT com$
 */

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_CHARS 10 * 1024 * 1024

/*
 * Borrowed from http://coding.derkeiler.com/Archive/Assembler/comp.lang.asm.x86/2007-03/msg00004.html
 * GNU Compiler syntax
 */
inline uint32_t bswap(uint32_t val)
{
    __asm__("bswap %0" : "=r" (val) : "0" (val));
    return val;
}

char * reverseAsm(const char * str)
{
    int i;
    int length = strlen(str);
    int dwordLength = length/4;

    if(length % 4 != 0)
    {
     printf("Error: Input string length must be multiple of 4: %d\n", length);  
     return NULL;
    }

    char * reversed_string = (char *) malloc(length+1);
    for(i = 0; i < dwordLength; i++)
    {
     *(((uint32_t *) reversed_string) + dwordLength - i - 1) = bswap(*(((uint32_t *) str) + i));
    }

    reversed_string[length] = '\0';

    return reversed_string;
}

char * reverse(const char * str)
{
    int i;
    int length = strlen(str);
    char * reversed_string = (char *) malloc(length+1);

    for(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(void)
{
    int i;
    char *reversed_str, *reversed_str2;
    clock_t start, total;
    char *str = (char *) malloc(MAX_CHARS+1);

    str[MAX_CHARS] = '\0';

    srand(time(0));

    for(i = 0; i < MAX_CHARS; i++)
    {
     str[i] = 'A' + rand() % 26;  
    }

    start = clock();
    reversed_str = reverse(str);
    total = clock() - start;
    if(reversed_str != NULL)
    {
     printf("Total clock ticks to reverse %d chars with pure C method: %d\n", MAX_CHARS, total); 
     free(reversed_str);
    }
    start = clock();
    reversed_str2 = reverseAsm(str);
    total = clock() - start;
    if(reversed_str2 != NULL)
    {
     printf("Total clock ticks to reverse %d chars with ASM+C method: %d\n", MAX_CHARS, total); 
     free(reversed_str2);
    }

    free(str);

    return 0;
}

The results on my old computer under Cygwin:

fer@fernando /cygdrive/c/tmp$ ./reverse.exe
Total clock ticks to reverse 10485760 chars with pure C method: 221
Total clock ticks to reverse 10485760 chars with ASM+C method: 140

Answer 15

String reversed in place, no temp variable.

static inline void
byteswap (char *a, char *b)
{
  *a = *a^*b;
  *b = *a^*b;
  *a = *a^*b;
}

void
reverse (char *string)
{
  char *end = string + strlen(string) - 1;

  while (string < end) {
    byteswap(string++, end--);
  }
}

Answer 16

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 17

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.

Answer 18

.

char * reverse(const char * str)
{
  if (!str)
    return NULL;

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

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

  return reversed_string;

}

Half the time but same complexity (note may be off by one error)

Answer 19

Above for loop has typo. Check of loop variable i should be <= instead of <, othrewise will fail for odd no of elements. for(int i = 0; i <= length/2; ++i)

Answer 20

You cannot (should not) do this:

string[i] ^= string[length - i] ^= string[i] ^= string[length - i];

From: http://en.wikipedia.org/wiki/XOR_swap_algorithm#Code_example

• *"This code has undefined behavior, since it modifies the lvalue x twice without an intervening sequence point.