Reversing C-Style Strings With Pointers

It's a common interview question to ask an applicant to reverse a c-style string, without using string utility functions. In practice, this is something you almost never do, as modern programming languages have nice, safe string classes and interfaces, most likely complete with their own string::reverse() methods.

However, the test has some value. Depending on how the applicant approaches the task, you can gauge his comfort level with pointers. You can get a feel for the applicant's efficiency with memory and operations. Do they reverse the string in place, or allocate new memory?

In particular, swapping the values of two variables, is an interesting sub-test. Can the applicant do this correctly? How do they choose to do it? They can do it in a separate function, with pointers, with references, etc.

Finally, testing. Does the applicant simply write an answer and say "tada"? Or do they try to walk through the code and test what it does, maybe catching mistakes or corner-cases?

As long as the applicant can correctly complete the task, there are no wrong answers. This test really elucidates their style and thought process.

Even though a person might scoff at such a "trivial" test that "doesn't prove anything," it turns out that the test is not so trivial for most programmers. Notably, most applicants cannot correctly complete this task the first time.

Now to the code:

1:  void reverse_str(char* str){  
2:       //Receive a c-style string, meaning a pointer to an array of type char,  
3:       //Reverse in place  
4:       char* lower=str;  
5:       char* upper=lower;            
6:       while (*upper!='\0')     //Searching for the end of a null-terminated string       
7:            upper++;       
8:       upper--;          //Decrement it; we want the last non-null element  
9:       while (upper>lower){       
10:            char temp=*lower;  
11:            *lower=*upper;  
12:            *upper=temp;                                          
13:            upper--;  
14:            lower++;  
15:       }  
16:  }  

In this example, I've used pointers. To find the length of the string, I iterate the pointer [upper] until I find the null-character. I then decrement this pointer, to the last non-null character.

Then, I swap the values of the lower and upper pointers, incrementing the lower and decrementing the upper, until they meet in the middle. And that's it.

If I wanted to be a little more elegant with my swapping, I might write a separate function to swap the values of the pointers. How might I do that?

1:  template<class T>  
2:  void swap(T* a, T* b){  
3:       //Swap the values of two pointers  
4:       T temp=*a;  
5:       *a=*b;  
6:       *b=temp;  
7:  }  

In this case, I've chosen to swap using pointers. So, lines 10-12 in reverse_str() would change to:

1:  swap(lower,upper);  

One other option could be to swap using references. It's actually pretty important that an applicant understands references in C++, as this is a common and integral feature of the language. [Maybe I'll do a follow-up entry on this at some point]. Here's a swap with references:

1:  template<class T>  
2:  void swap(T& a, T& b){  
3:       //Swap the values of two variables  
4:       T temp=a;  
5:       a=b;  
6:       b=temp;  
7:  }  

In this case, lines 10-12 of reverse_str() would need the pointers to be dereferenced:

1:  swap(*lower,*upper);  

So yeah, there you go. There are myriads of other ways to approach this problem. For such a seemingly simple task, you get a lot of mileage and information about a software engineer.