Silly code snippets useful for interviews

The never ending process of interviewing with prospective employers often involves silly little logic tests. I'm going to start a series on how to solve some of these problems using standard C. These entries assume you have some basic understand of C and pointers. For the following example you should understand the basics of how C strings work.


Reverse a string for me son

To kick the series off I'm going to solve a very common problem that comes up during interviews, reversing a string. While not a practical problem, what employers are trying to determine is how efficiently you solve it.

If the interviewer does not provide you with any function prototype, then you should ask them to do so. If they tell you to make it up yourself then you have a couple of choices. I'm going to keep things simple in this post and assume that you can just pass in a character array and its length. These example do not require the use of any library functions either. Your interviewer may want you to determine the string length, either manually or using strings.h. I'm not going to talk about that for this example and just focus on the actual reversal of the string.

One seemingly easy approach to reversing a string is to simply walk the string backwards, appending each character to a new string, like this.

char * simpleReverse(const char string[], short stringLength)
											{
											    // Create a buffer for our reversed string.
											    char *reversedString = malloc(stringLength);
											
											    // Start at the end of the string and copy each character to 
											    // the new string at the opposing position.
											    for (short index = stringLength-1; index >= 0; index--)
											   {
											        short reversedIndex = stringLength - 1 - index;
											        reversedString[reversedIndex] = string[index];
											    }
											
											    // Terminate the new string.
											    reversedString[stringLength] = '\0';
											    return reversedString;
											}
											

This solution seems is simple, start at the end of the string and copy each character into the reversed buffer. The main problem with this solution is it requires us to have an additional buffer for the entire reversed string. Assuming the interviewer didn't want you to return a new character array, this function could be modified as follows.

void simpleInPlaceReverse(char string[], short stringLength)
											{
											    char reversedString[stringLength];
											
											    // Start at the end of the string and copy each character to 
											    // the new string at the opposing position.
											    for (short index = stringLength-1; index >= 0; index--)
											    {
											        short reversedIndex = stringLength - 1 - index;
											        reversedString[reversedIndex] = string[index];
											    }
											
											    // Loop back over the string and copy in the reversed characters.
											    for (short index = 0; index < stringLength; index ++)
											    {
											        string[index] = reversedString[index];
											    }
											}
											

Now things are getting messy. We are still creating the string buffer and reversing the string character by character, but then we have to loop back over the string and copy each character into the source string. Also it isn't very clever and, well, during an interview you want to impress your interviewer as being the clever problem solving type. 

So lets take another shot at solving this. How about instead of just grabbing a character and copying it to another buffer and then back again, we actually just move the character around the buffer we are already using? Additionally why don't we try to do more work per iteration and get this sucker reversed in half the amount of loops? We can do that like this.

void coolReverse(char string[], short stringLength)
											{
											    // Start out with indexes to the first and last characters. Stop when we have 
											    // reached the middle of the string and swapped all characters.
											    for (short front = 0, back = stringLength - 1; front < back; front++,back--)
											    {
											        char swap = string[front];
											        string[front] = string[back];
											        string[back] = swap;
											    }
											}
											

We start off with two counters. The first initially points to the first character and the second the last character. This could be done with a single index but then we would have to calculate the opposing index in both the iteration test and in the loop body.

Once inside the loop, we have a character buffer that we copy the initial character into. We take the opposing character, which is the last character on the first iteration, and copy it into the initial character's position. Finally we copy the buffered character into the opposing character's position. After each iteration we increment the "front" and decrement the "back", thus working from the ends of the string toward the middle at two characters per iteration. We terminate the loop once we have reached the middle of the string.

This solution has the added bonus of not performing work for the middle character of odd length strings. We don't have to move the null terminator around either. It is also half the amount of code, which means you can impress your interviewer that much faster.

You might think, well I can be even cooler and use bitwise operators! How can I do that?

void uncoolBitwiseReverse(char string[], short stringLength)
											{
											    for (short front = 0, back = stringLength - 1; front < back; front++,back--)
											    {
											        string[front] ^= string[back];
											        string[back] ^= string[front];
											        string[front] ^= string[back];
											    }
											}

Don't do it, ever. Not only is this confusing, it is actually inefficient to write code like this. If you compile the programs using optimization you'll see that using the bitwise operations will actually generate more lines of code. Compilers are S-M-R-T, rely on them and they can save you a bunch of time.

You can start learning the nitty gritty of bitwise operations here.

So there you go. Next time someone asks you to reverse a string you can do it in style using a measly 4 bytes of memory overhead with only 4 lines of C code!

Even your worst day has a lesson to learn.