Question: Reverse a string in C using as little additional memory as possible.
Answer: The first solution needs the size of a char and size of two integers, all of which will be allocated from the stack. This solution is the most commonly accepted “good” solution. Here is the code.
void reverseString(char* str)
{
int i, j;
char temp;
i=j=temp=0;
j=strlen(str)-1;
for (i=0; i<j; i++, j--)
{
temp=str[i];
str[i]=str[j];
str[j]=temp;
}
}
The second solution is slightly better than the first as it does not need the char space. It uses bitmanipulation (XOR in this case) to swap the chars in place.
void reverseStringBetter(char* str)
{
int i, j;
i=j=0;
j=strlen(str)-1;
for (i=0; i<j; i++, j--)
{
str[i] ^= str[j] ;
str[j] ^= str[i] ;
str[i] ^= str[j] ;
}
}
Even though the second solution uses less space, the first one is probably a better solution in terms of readability and maintainability. The compilers are very advanced now and are able to reduce the swap instructions in the first solution into a single execution step. However, the same might not happen for the second solution so in real life situations, it is better to use the first solution although the second solution seems smarter and better theoretically.
If you have any questions, please feel free to send me an email at [email protected]. If you have any interview questions which you feel would benefit others, I would love to hear about it.
If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:
I don’t know C but couldn’t j just be computed on the fly as strlen(str)-1-i to use less stack memory?
@bubu
I’ve been in a technical interview where I’ve had to argue exactly that. My question was in fact the rather more famous, write a swap routine to swap over two bytes.
My answer was to use the same code as above, tmp = a, a = b, b = tmp kind of thing.
The interviewer asked whether I knew of another way of swapping that wouldn’t use the extra byte. I explained as @bubu did that the XOR trick is probably always the wrong solution, since it didn’t allow the much smarter compiler writers to do their jobs as easily.
So, moral of the story is that it’s good to know about the XOR trick, even if it’s just to explain why you wouldn’t use it.
As an interviewer, if somebody used the XOR trick, I would ask them to explain why it works, and when they would use it.
Second solution is not better, and definitely not “smarter”. char space needed in first solution will not be allocated on stack. Modern C/C++ compilers will use CPU registers to store short temporary variables. So there is no need to be “smarter” when you are really not – you will be just showing that you don’t know nothing about modern C/C++ compilers.
That is a very good point you make there. Thanks for pointing it out.
strlen returns size_t (or unsigned int) not int.
You should avoid initialization of j to 0 and then assigning a value (“two” operations)
instead initialization of “j” variable should be written as:
const size_t j = strlen(str) – 1;
“one” operation.