String Reverse Without Declaring a Local Variable or calling another function?

Factual Questions
1

A friend of mine at work once interviewed at Google and one of the questions they asked him was how to reverse a string in C without declaring a local variable or calling another function.

You assume you are writing a function which is passed a char * containing a nul terminated string. How to reverse it without declaring a local variable?

My first statement to him is, “well, I need need a variable for swap, end of story.” He says no, you can use the nil character for swap storage, that isn’t the problem. I think, well, then I can use characters after the nil as well. As long as it was allocated from heap I’m most likely going to be ok. But then I start to think, ok, smart guy, how do know how long your string is?

I can do pointer arithmetic but I don’t have anything to add or substract from my pointer. I can increment my pointer but how do I know how many times I’ve done so?

He said he missed the question in the interview. He said he told the interviewer he felt it was impossible. The interviewer asked him how he could begin to approach it. My friend said “maybe through recursion”.

That excited me a little bit. If my function that I write returns an integer or char type, that is sort of like getting a storage allocated on the stack without declaring a local variable. If I recurse then I can retrieve a value returned, but I have to somehow have a terminating condition. What could that be?

Anyone ever confronted this problem? Any ideas on where to go further? I am quite certain it is solvable but recursion makes my head hurt and I really can’t think how to get any more information into my function.

2

I had a worse question come up when I was interviewing with Silicon Spice a few years back. (You’ve probably never heard of them. Good riddance.) They asked me how to reverse the word order of a string of arbitrary length, without allocating any memory. The right answer was to reverse the string, and then to reverse each word within the reversed string.
Anyway, this other tidbit may help: Here’s how you swap two variables, x and y, without using a “temp” variable for swap storage:


x ^= y;
y ^= x;
x ^= y;

The eXclusive OR operation will preserve all your bits in the end.

3

Yes but in my example I don’t have two variables. I have only one char * so this method would not work. Anyway the above method would work only on numeric types, not strings.

4

Wait, I didn’t think this through enough. I could also say:
*p >= *p++;
*p >= *p[-1];
*p[-1] >= *p;

It seems useful at first, but if I increment my pointer there is really no way of figuring out where the beginning of the string was…how do I move a character all the way back there?

5

My C has really gone to pot. I think I meant something more like:

*p >= *++p;
*p >= p[-1];
p[-1] >= *p;

6

And you meant ^= , not >=. I hope.

7

Yes that too.

8

Here’s a little hint for a solution that I think ought to work:Recursion is a good idea. Each iteration of the recursion should just move one character to the end of the string.

Here’s a snippet of code that might help further:void reverse( char *p ) {if ( *p ) {[INDENT]reverse(p+1);
// do something here
}[/INDENT]}
Post again if you want the rest.

9

Assuming recursion is allowed, you can recursively reverse the substring starting at the second element and then xor-swap first element to the end.



void reverse(char *s)
{
   if (*s == 0) return;

   reverse(s+1);

   while (*(++s) != 0)
   {
      *s ^= *(s-1)
      *(s-1) ^= *s;
      *s ^= *(s-1);
   }
}
10

Hmmm, I ruined Omphaloskeptic’s spoiler. Are answers to these type of questions supposed to be put in a spoiler box?

11

That’s the solution I had in mind as well.

Can it be done without recursion? I can do it without recursion if I allow the string to have a little extra room (two extra characters on the end) but I can’t see how to do it with less than that.

12

Yes tracer gave me the rest…very elegant thanks folks.

13

Can you explain that? I initally was thinking along these lines, but I get lost in the particulars. Since I cannot know where those extra characters are in relation to my pointer (i cannot store the offset anywhere) I can’t see how to make any use of them.

14

With a little extra room, you can pretend that the string is a Turing-machine tape, with the string pointer being the head and the extra NULs being interpreted as tape end-marks. Suppose you start with string
0abcd00
where I use lowercase letters to represent nonzero string characters and 0 to represent a NUL, so that the string has an extra null character at beginning and end. (If these are not initialized to zero we can add some steps to do this first.) The underlined character is the one pointed to by our char *. (At first I thought I could do it with all the NULs at the end, but I don’t think I can do that any more.)

Now we swap characters and move the pointer to the right, until we get to a NUL:
0abcd00
0bacd00
0bcad00
0bcda00
0bcd0a0
Now move left across the middle NUL to the leftmost NUL
0bcd0a0
0bcd0a0
0bcd0a0
0bcd0a0
0bcd0a0
move the pointer to the right, and repeat as long as the current position isn’t a NUL:
0bcd0a0
…
0cd0ba0
…
0d0cba0
00dcba0
Now just move right one more time and end.
00dcba0

15

This is what I would say is a good answer to that question:

“I suppose it could be done thru recursion or some tricky pointer manipulation. But neither of those would be as efficient or as comprehensible as a straightforward process using a swap variable. So it would be better to use the space needed for a variable. And if a rather unusual operation like reversing strings happens to be a frequent part of the specific algorithm, then I would suggest calling a reverse subroutine or a local function.”

Of course, this is from the viewpoint of an actual real-world practical programmer, which may not be relevant.

This is an interview question, after all – they don’t have to make any sense! (And seldom do.)

16

t-bonham, you took the words right out of my mouth. The world does not need another Duff’s device, and the IOCCC can get along just fine without `real-world’ programmers helping it out.

Plus, your code is only guaranteed to work if you can be sure you’ll only ever have strings composed of unsigned chars. Otherwise, you can inadvertantly create a trap representation and crash the machine.

That, or invoke nasal demons.

In any case, this isn’t really a programming exercise. Google is (presumably and hopefully) testing the knowledge of logic and algorithm design among its applicants, instead of fishing for new ways to solve an old problem.

(As a final note, recursion loses on long strings. How long it’s impossible to tell without knowing the specifics of the machine’s state at the time of the first call, but almost any recursive function in C is a stack smash waiting to happen.)

17

Imagine a very memory-limited program, something that has oodles and oodles of clock cycles to support it, but can only use 1k of RAM for whatever reason. Think of something like GMail, where the size of the application is crucial to its speed. If you can keep the Java application underneath the size of one TCP/IP packet (!!!) and still build in all the features you want, then the execution is performed at GHz speeds, where ten–or even a hundred–clock cycles are well below the threshhold of human perception. In fact, slowing it down just a little might even make the e-mail server’s job easier, since requests won’t come quite as often.

Granted, it’s not a terribly realistic scenario, but it’s out there at the two-sigma end of “things you might be asked to hack together at a normal company”. Google wants an entire staff composed of people who can do things out at that end of the spectrum, so when they say “let’s innovate,” nobody on the team gets too worried.

18

What you said is certainly true; I just wanted to add that in the above scenario the use of recursion is about the worst thing you can do. It is certainly more memory efficient to introduce a few local variables then to “abuse” the stack.

I also think Google simply wants to hire employees that have a firm understanding of computing algorithms. String reversal by recursion is something that is often given as an example (along with computing n!) when introducing students/trainees to recursion, because it is short and relatively easy to understand, although non recursive methods are much more efficient in “production” code.
The swapping of two variables by using XOR is, however, IMO more of a holdover from assembler days, like the use of XORing a variable with itself to set it to zero without loading 0 in a register on machines that have no hardwired 0 register. Current compilers should be smart enough to optimize code that way if necessary, and trying to do it yourself could confuse the optimizer.

19

You all missed the obvious answer. Declare GLOBAL variables to hold the swap value and string length.

-lv

20

That’s a very bad solution!
You should not define a variable as GLOBAL when it is used only as a temp swap variable in a local piece of code.

Technically, it does meet the original question. And that may be the tricky answer they want, since they specified “without declaring a local variable” instead of “without declaring a variable”.

But it’s still a very unprofessional way to code this.
But then, what do interview questions have to do with professional coding practices?