Reversing A String - The worse way, The better way

A common programming interview question is to reverse a string. A common first approach is to copy the contents of the string into a temporary string in reverse order, and then copy the temporary string over the original string. Do this in an interview, and you'll be informed that while your solution is correct, it can be much better. Doing it in this fashion is very inefficient, but it is still nonetheless a good place to start. As always, solve the problem first, then optimize. The naive solution would look something like this:



At this point, the interviewer is going to ask you to perform the reversing "in-place" meaning "do it all in one pass of the string, no double-pass copying shenanigans!"

So, how do we accomplish this? A basic swap should immediately come to mind. You need to swap pairs of characters in the string as you iterate over it until no more pairs exist. But, how to know when you've reached that point? Sure, you could keep track of indices of the string that have been swapped, but at that point you're diverging toward the inefficiency of the first solution because you'd have to do a lookup in the index table each time you attempted a swap, and that gets slower as your string becomes larger. So, storing indices is out. What else can we do? Well, let's see if there is an algorithm behind this.

Given the string "abc", what can we deduct about which pairs should be swapped?

'a' and 'c' get swapped, leaving us with 'b'. Clearly, we see there is nothing else to swap with, but how would we know this internally, from a source code level? The key lies in the positions of the characters in relation to the end of the string. We never want to swap 2 characters unless the location of the second character is > the location of the first character. Using our string "abc", 'a' is located at position 0 and 'c' at position 2. 'b' is located at position 1, but the character at position 2 has already been swapped.

To compute this mathematically, you do this:

firstIndex = 0
secondIndex = length of the string - 1
while secondIndex > firstIndex:
swap
increment firstIndex
decrement secondIndex
loop

Putting this into C, we have the following, efficient reverse algorithm:



And here is the output, using both versions consecutively on the same string (reverses it, then reverses it again):

$ ./reverse
original: abc
reverse: cba
reverse2: abc

Hopefully this has been helpful to you. Remember, the most obvious solution is most likely not the most efficient.

When Errors Make Absolutely No Sense...

...you're probably doing something stupid.


I'm working on a new project (C++), and the setup is fairly simple:

I've got 5 implementation files, a utilities header file, plus my main file. Of those implementation files, 2 of them consist only of utility functions I've previously written.

In my utilities header, I've got 3 basic structures, plus an enum. 2 of the structures contain 1 very basic function defined within them.

Now that you have the details, let's get on to the issue...

I needed to add a function to determine the intersection (if any) between 2 lines in 2d space. Naturally, already having this utils.h file, I decided to throw it in there. I probably shouldn't have, as it is relatively long and complicated enough that the compiler wasn't going to be able to inline it, but at the time I just threw it in there and tried to do a quick compile:

/tmp/ccnsMHTQ.o: In function `checkIntersection(Point2d&, Point2d&, Point2d&, Point2&)':
VerticalPattern.cpp:(.text+0x2e1): multiple definition of `checkIntersection(Point2d&, Point2d&, Point2d&, Point2d&)'
/tmp/ccqHjPfS.o:HorizontalPattern.cpp:(.text+0x20b): first defined here

/tmp/cc1AN3z7.o: In function `checkIntersection(Point2d&, Point2d&, Point2d&, Point2d&)':
Enemy.cpp:(.text+0x8e): multiple definition of `checkIntersection(Point2d&, Point2d&, Point2d&, Point2d&)'
/tmp/ccqHjPfS.o:HorizontalPattern.cpp:(.text+0x20b): first defined here

/tmp/cc6 _16 _11ouOwL.o: In function `checkIntersection(Point2d&, Point2d&, Point2d&, Point2d&)':
main.cpp:(.text+0x1ba): multiple definition of `checkIntersection(Point2d&, Point2d&, Point2d&, Point2d&)'
/tmp/ccqHjPfS.o:HorizontalPattern.cpp:(.text+0x20b): first defined here

collect2: ld returned 1 exit status

Huh? That function certainly isn't defined anywhere other than utils.h. So, what gives? My first thought was that I screwed up a header guard somewhere and that coupled with me throwing the definition of the function into the .h file may be causing some issues. So, I checked...

All header guards were fine. Then I started to wonder if it could be a circular dependency of sorts. But, why then is the newly added function the only one causing the linker error? Wouldn't everything else in utils.h also be causing problems? I decide to conduct a test to find out:

I added a very simple function definition to utils.h and placed it above the definition of checkIntersection():

void foo() { int x = 2; }

A quick re-compile, and...

I got the same error as before, except now also with respect to foo(). Looking back over utils.h, it becomes clear that the compiler is inlining the functions declared within my structures. This makes sense, because member functions defined inside of a class definition are implicitly inlined. Inlining means that the functions are replaced by inserting the function bodies at the locations in which they are called. This means the linker never sees them, thus has no reason to complain about them in my situation.

At this point, I have enough information to construct a simple test case to illustrate the issue and better debug it. I need the following setup:

* A utils.h header file that contains a structure which is composed of a trivial data member as well as a function.

* Also in that utils.h file, I need to define a free standing function.

* Lastly, I need to have 2 additional source files, both of which include utils.h, one of which can be the file that holds my main method.

Once constructed, I'm left with the following:



O.K., time to try to build it and see what we get:

/tmp/ccwuqYve.o: In function `utilsFoo()':
foo.cpp:(.text+0x0): multiple definition of `utilsFoo()'

/tmp/ccCIDNQe.o:main.cpp:(.text+0x0): first defined here
collect2: ld returned 1 exit status

Good. The test case is valid. main.cpp includes both foo.h and utils.h, and foo.h also includes utils.h, thus multiple definitions. Evidently, I'm making a false assumption about what I'm doing, what the header guards are doing, or both... and you know what they say about assuming. Time to stop assuming and starting knowing:

Header guards only prevent multiple definitions within a single translation unit. Take this situation for example:

foo.h - includes utils.h, bar.h
bar.h - includes utils.h

Header guards prevent the contents of utils.h from being included more than once within foo.h (a single translation unit): Once from directly including utils.h, and again when it includes bar.h which in turn includes utils.h.

So, isn't that what I was doing in my example? No, not at all. I was trying to rely on header guards to prevent multiple translation units from defining the same function. After compilation, main.o and foo.o both contain code for utilsFoo() because both main.cpp and foo.cpp include utils.h, which is where utilsFoo() is defined. It isn't being defined more than once per-file, but rather multiple times across all files (translation units). Thus, the linker has multiple object files that all have code for utilsFoo().

So, why does sticking the definition of utilsFoo() into an implementation file as opposed to a header file fix the issue? Because in that case, that implementation file is the only object file that has code for utilsFoo(). When other translation units include utils.h, they are simply making the declaration of utilsFoo() visible to themselves. That is to say, they are making themselves aware that the function exists and can be called, but they aren't pulling in the code for the function.

I feel much better now. Sure, I knew how to fix this from the outset, but it was more important to me to know why I needed to fix it.