void reverse(char* str)
{
if (str == NULL || *str == '\0') return;
char *tail = str;
while (*tail != '\0')
{
tail++;
}
char tempChar;
tail--;
while (str < tail)
{
tempChar = *tail;
*tail = *str;
*str = tempChar;
str++;
tail--;
}
return;
}What does the above function do? Well, if you paid attention to the title, or if you can read C++, this should be fairly obvious.
The method in question is called reverse and passed to the method is the sole pointer to a string. This method assumes that the string in question will be a basic ASCII string that is null terminated. In fact, that what '\0' represents. The null terminator.
Where are the comments? Well, since the code is fairly simple, and after reading a blog essay by Steve Yegge, the comments were left out. The essay in question is here: Portrait of a N00b. I'll forgive the perceived insult because Steve Yegge is right: I'm a n00b. Besides, had I documented the method with enough comments to double the line-count, I wouldn't be able to write a descriptive blog post about my thought process going into the method, now, would I?
The original problem once again comes from McDowell (2012).
Implement a function void reverse(char* str) in C or C++ which reverses a null-terminated string.Now, that question seems pretty straightforward. The author's solution given in the book is a little different from mine in trivial items. The logic is exactly the same. That made me very proud, until Mr. Yegge reminded me that I am still a n00b at programming compared to a two-decade veteran who has worked for Amazon and Google. Again, not insulted, but now blissfully aware of how much harder I need to study outside of and in addition to my core classes at Baker College if I ever hope of landing an offer with one of the Big Four.
Had this been an actual interview question, I would have asked a few questions before coding this. Because these questions are from an interview preparation book, I can not unfortunately ask any questions, but only make assertions. From the problem, the string is known to be null-terminated. What I did not know was what encodings this method should handle. My assertion was the string would be a basic ASCII string and not Unicode. I would have also asked if I was allowed to declare additional pointers and variables within the method. My assertion was that I was allowed to. The reason I would have asked this question is that I've seen message board postings with a similar problem that gives the same method signature, but adds the qualifier that no additional pointers or variables may be declared. This solution came together in ten minutes, and was tested in two. Had this been an actual interview, I would have been able to write it, test it, and explain what I was doing within the confines of the interview. If I was not able to declare any local pointers or temporary variables, this would have taken much longer and probably would have overran the time constraints of said interview.
Starting off, the first line of code is just basic optimization. If we were given a pointer that points to NOTHING, or to a null-terminator character itself, it means we have no string to work with. Nothing more is needed, so we return the control to the calling method. The method signature also states we return nothing, hence no error code such as "return 1;".
Yes, Mr. Yegge, I am a two-year old explaining how this big scary programming world works so that I know I understand it. At least I'm following one of your blogging rules, which is write a blog. :D
The next line declares a new pointer called tail and sets it to the address of the same starting character pointed to by str. So far, the time complexity of the method is O(1).
From here, we need to increment the tail pointer in order to find the null-terminator character. After that, we decrement the tail pointer so that it points to the last non-terminator character in the string. This loop changes the method time complexity to O(n) where n is the number of characters in our string. I saw no reason to limit how large the string can be that is passed. If I had, I would have kept track of how many times we incremented the tail pointer and then checked to see if the string fell into the confines of our arbitrary limit.
Now that the tail is found, we simply switch the first character, pointed to by str, and the last character, pointed to by tail. Now, we increment str and decrement tail, so that they both move toward the middle of the string, and swap each character again. We keep doing this until str and tail are at the same memory address or have passed each other. This means that the entire string is now reversed.
The overall time complexity of the method reduces to O(n). This means it scales linearly as the number of characters in the string gets larger. I see no way to make this O(1) constant time. If any industry veteran out there is reading this and knows a trick to do so, please feel free to share. I love it when n00bs like me are mentored.
The code I provided is my own code. It is not elegant, but simply straightforward. I chose to implement a "quick and dirty" solution rather than trying to hack the compiler to achieve the fastest possible run time. Depending on the project, "quick and dirty" may have saved the company some money by not devoting days to optimizing something that shouldn't break the overall project.
If this does break the project, then methinks I'm doomed...
Reference:
McDowell, G. L. (2012). Cracking the coding interview: 150 programming questions and solutions (5th ed.). Career Cup: Palo Alto.
