Fog Creek Software
Discussion Board




in place string reversal

Hi, In Joel's Guerilla Guide to Hiring he suggests several C programming problems which the interviewee can answer. The first on the list is to reverse a string in place. See http://www.joelonsoftware.com/articles/fog0000000073.html

To be honest I'm not sure what in-place means. My background is Elect. Eng not CompSci. From definitions on the web I've gathered that it means to reverse the string without using any storage locations other than the string itself.I've come up with several solns,some iterative, others recursive, but all using a temporay var. Anybody any ideas how to do this correctly?

john oliver
Thursday, October 14, 2004

I don't think this can possibly mean "With no external memory storage"--there's no way you could possibly reverse a String without using even a single local variable. What I do think it means is doing it without creating another String, or another data structure that approximates a String (such as a numerical encoding of a String).

This only makes sense in languages, like C++, where Strings are mutable objects. My language is Java, in which Strings are immutable, so I couldn't do exactly this. I could do something fairly similar with a StringBuffer or array of chars, but I won't bother. Instead, I'll write up a bit of pseudocode (this assumes the String, myString, is represented as an array of chars):

int firstPos=0;
int lastPos=myString.length - 1;
while (firstPos < lastPos)
{
  char temp=myString[firstPos];
  myString[firstPos]=myString[lastPos];
  myString[lastPos]=temp;
  firstPos++;
  lastPos--;
}

That (fixed so the syntax is legal for whatever language you're using) will do it. Note that there is a bit of external storage, but just two ints (to hold locations in the String) and one local char (as a temporary storage location to facilitate the swap). What this doesn't contain is anything like a second String.

I think what this is meant to test is the "temp" trick, which is a very useful (if simple) programming trick.

Avrom Roy-Faderman
Thursday, October 14, 2004

Thanks, Avrom, much appreciated.

John Oliver
Friday, October 15, 2004

You can get away without using the temporary variable if you use the "xor-swap" trick.

a ^= b; /* a^b, b */
b ^= a; /* a^b, b^(a^b)=a */
a ^= b; /* (a^b)^a=b, a */

rjp
Thursday, October 21, 2004

When feeling perverse, I always like reducing the XOR trick to: a ^= b ^= a ^= b;

Disgusting, no?

Andrew
Thursday, October 21, 2004

OK, that's very cool, and is a trick I'd never heard of before.

(I take it
a ^= b
means

a = a bitwise-XOR b

right?)

But you still need a temporary variable to store the index, no?

Avrom Roy-Faderman
Thursday, October 21, 2004

You would need to define what a string is.  If it's a C string, you could just make the pointer to the beginning of the string point to the end...

Compiler_Blues
Sunday, October 24, 2004

Life's not that simple.

If you just make the pointer to point to the end of the string
1. Everybody would expect the next char to be at position end + 1, while it is at position end - 1.
2. Even if you manage this problem,  at position start - 1 there most likely won't be a terminating 0.

Luckily, either at position end or end + 1 (depends on your definition of "end") there is a 0, so at least the system won't crash :-)

Gerd Riesselmann
Monday, October 25, 2004

void strRev(char *s)
{
    for(char *end = s + (strlen(s) - 1); (end > s) ; --end, ++s)
    {
        char tmpChar = (*s);
        (*s) = (*end);
        (*end) = tmpChar;
    }
}

Bart Park
Thursday, November 04, 2004

I guess the perverse version would be?

void strRev(char *s)
{
    for(char *end = s + (strlen(s) - 1); (end > s) ; --end, ++s)
    {
        (*s) ^= (*end) ^= (*s) ^= (*end);
    }
}

Bart Park
Thursday, November 04, 2004

Hey, you have two braces more than you need there.  And you can drop all the whitespace, put it  on one line, and cut all identifiers down to one character if you *really* want to ruin your chance in the hypothetical interview... ;)

Foo
Sunday, November 07, 2004

Actually, I've refined it a bit more :-)

void strRev(char *s)
{
    for(char *end = s + (strlen(s) - 1); (end > s) ; (*s++) ^= (*end) ^=(*s) ^= (*end--));
}

You say ruined my chances for the interview. I say if they are really interested in hard core C stuff, this is a work of art.

Bart Park
Sunday, November 07, 2004

And to extend it for Unicode strings:

void wstrRev(wchar_t *s)
{
    for(wchar_t *end = s + ((wstrlen(s) - 1) * sizeof(wchar_t)); (end > s) ; end-= sizeof(wchar_t), s+= sizeof(wchar_t))
    {
        (*s) ^= (*end) ^= (*s) ^= (*end);
    }
}

Gord Peters
Tuesday, November 09, 2004

Oops, that should be wcslen() instead of wstrlen() in my last post.  I think wstrlen() is available on some systems, but wcslen() is more standard.

Gord Peters
Tuesday, November 09, 2004

Yikes, I've been working in Java too long.  Forgot that the value of a pointer to an array is incremented/decrimented by array element, not by byte.  Hence, the proper version of the above:

void wcsrev(wchar_t *s)
{
    for(wchar_t *end= s + (wcslen(s) - 1); (end > s) ; (*s++) ^= (*end) ^=(*s) ^= (*end--));
}

Gord Peters
Tuesday, November 09, 2004

I think you could get even more creative with it by using math and ASCII codes.

I am Jack's string solution
Wednesday, November 17, 2004

that only works with UCS-2. What about UTF-16?

Heck, how about UTF-8. That's pretty easy not-in-place, but gives me a headache thinking about getting it right in-place.

mb
Thursday, November 18, 2004

From reading Joel's article on this, I had thought the point of the question was esoteric pointer knowledge and the slightly skewed thinking that goes along those lines. As he mentions in several places, some people just don't get pointers. It's good to know if somebody gets them or not.

None of this sort of thing would work very well for any unicode or multibyte stuff. If that was the point, then it would look totally different. You certainly couldn't do the one liner in those cases, I believe. Especially unicode. Unless, of course, you wrote the classes that would allow you to do the things that the one liner does. Couldn't do the xor swap in that case, though. One problem, from my limited understanding of unicode, would be that in the same string different characters can be encoded by different numbers of bytes. That would throw a nice little monkey wrench in the the single line swap.

Bart Park
Friday, November 19, 2004

ucs-2 is just as easy as ASCII.

for more, see here http://www.joelonsoftware.com/articles/Unicode.html

mb
Friday, November 19, 2004

Just above my post you mention that UTF-8 is giving you a headache. I understand that ucs-2 can be done just as you say and Joel mentions by using wchar_t, but that is making an encoding assumption. You can only do that if you have control over all the input or if you take the time to change encodings to one you know will work.

At that point, I think you would be better off with just doing the swap the old faashioned way by using a temporary variable and walking the string.

Would XOR swapping work with ucs-2? I assume it should, but I haven't actually ever tried it.

Bart Park
Monday, November 22, 2004

Here would be an easy way to do it with a C string:
Just shift all the characters over by 1, add a null to
the old beginning of the string and return a pointer to
the old end of the string.

char *reverseString(char *str)
{
  if (str)
  {
      int length = strlen(str)+1;
      for (int i=length; i>0; i--)
      {
        str[i] = str[i-1]; 
      }
      str[0] = NULL;
      return &str[length];
  }
  else
  {
      return NULL;
  }
}

John Jenkins
Thursday, December 23, 2004

Except the previous method requires the hardware to be capable of reading your mind to determine which way to read the string, forwards or backwards. If you find one, let me know. I've been looking for something that will always do what I mean.

DaveH
Tuesday, January 04, 2005

    XOR trick fails if the items being XORed are identical.

gg
Thursday, January 27, 2005

*  Recent Topics

*  Fog Creek Home