Converting a string to an integer is another classic interview question. I was asked this one during my Microsoft interview in 1991 and I was so nervous I butchered it badly. I still remember sweating bullets even now, almost twenty years later. Fortunately, the manager took pity and allowed me to play a debugging exercise where I discovered the mistakes I had made.
The function atoi is shorthand for ascii to integer. You call it like this:
int fooval = atoi("123");
It can be written in a few lines of code, but it hinges on your awareness of the Ascii table. ASCII stand for American Standard Code for Information Interchange; it’s the fundamental building block that allows computers to exchange information. There are codes for uppercase alphanumeric characters (A-Z) in the range 65-90, and the lowercase alphanumeric characters (a-z) in the range 97-122. Numerals 0-9 are in the range 48-57. Your knowledge of the Ascii table can help you not only with these interview coding exercises, but many others as well.
Another concept that will aid you is the knowledge of how C works with character pointers:
char* index = "123";
The index variable is a pointer, but it points at the first character in the char string (1). If you increment the index, it will point at the next char value (2). You can determine when you’ve reached the end of the string by testing the value to see if it is the NULL character, \0. All C strings are terminated by this value. You have to remember to look for the NULL character when searching C strings, and if you are creating a new string, you have to remember to place that at the end.
Now that we are armed with this knowledge, we can write atoi:
int atoi( char* pStr )
{
int iRetVal = 0;
if ( pStr )
{
while ( *pStr && *pStr <= '9' && *pStr >= '0' )
{
iRetVal = (iRetVal * 10) + (*pStr - '0');
pStr++;
}
}
return iRetVal;
}
This implementation starts off by clearing out iRetVal with 0. In case the string is NULL or empty, the return value will be 0. We loop through the string, looking for numeric characters. When we encounter one, we determine the integer value (*pstr - ‘0’) and add that iRetVal. iRetVal gets multiplied by 10 to make the correct scale value. Note that the first time around, iRetVal is 0. Finally, we increment the char index to move to the next character in the string.
This is pretty simple and straightforward, although it isn’t perfect. What if there is a negative sign in the string (“-123’). Whenever you write code during an interview, it won’t be perfect. It’s important to be able to identify weaknesses and bugs in your code to the interviewer.
The reverse function for integer to ascii, itoa, is a bit more complex. I was asked to write this just a couple of years ago during an interview. Funny enough, the engineer who asked me to write it was an ex-Microsoft engineer. I solved it correctly for a default case where the number is base 10. He showed me a way to write it for base 10, base 16, or any base value. You will call itoa like this:
printf("itoa(123) = %s\n",itoa(123));
This is the default way of calling itoa. The return value is “123” which is output by the printf function. But, as this ex-Microsoft engineer asked me, what if we wanted to output the hexadecimal value, “7b”? You would call an overloaded itoa function like this, with the base (16 for hexadecimal) like this:
printf("itoa(123) = %s\n",itoa(123, 16));
Now let’s write the function. We will actually write two functions here. If you do this during interview, you will score extra points. First the itoa function that takes the base as the second parameter:
char *itoa(int n, int b)
{
static char digits[] = "0123456789abcdefghijklmnopqrstuvwxyz";
int i=0, sign;
char *s = new char[100];
if ((sign = n) < 0)
n = -n;
do {
s[i++] = digits[n % b];
} while ((n /= b) > 0);
if (sign < 0)
s[i++] = '-';
s[i] = '\0';
return strrev(s);
}
And now the default itoa function, which assumes the most common case, where we call it for base 10 numbers:
char *itoa(int n)
{
return itoa(n, 10);
}
This itoa function with the base parameter makes use of a character array called digits. This array contains the values 0-9, followed by the lowercase alphanumeric values a-z. These values will be used for the individual characters in the return string value:
static char digits[] = "0123456789abcdefghijklmnopqrstuvwxyz";
The first thing we need to do is check the sign of the number we need to convert. Is it less than 0? If so, we’ll need to remember this for later.
Now we do a tight compact loop through number n:
do {
s[i++] = digits[n % b];
} while ((n /= b) > 0);
The char string holding the return value starts getting the individual digits chopped off number n. We chop them off using the modulus operator: %. When b is set to 10 and n is 123, n % b becomes 123 mod 10. The value of that mod is 3. Index 3 inside the digits array is the character ‘3’.
The loop prunes the digits off the number n. N gets reduced (by the base number) as the loop goes on with the expression “n /= b”. When N is 123, the first time through this loop, it becomes 12.
Let’s picture what happens to the return char string s and integer n as the loop progresses:
First pass: n = 12, s = “3”
Second pass: n = 1, s = “32”
Third pass: n = 0, s = “321”
The loop terminates when n reaches 0. Now we take a look at the sign value. If the number was negative, we had the char minus sign (1). Don’t forget to mark the end of the string with the NULL character as I mentioned previously.
Now we almost have the return string value, except it is in reverse. You can call strrev to reverse it back to the proper form and return the value.
This may lead into writing a function to reverse a string value…which I will write next time.
