Interview Questions

Atoi

Convert string to integer.

View Solution

Algorithm concept

'Atoi' stands for 'ascii to integer' and converts ASCII characters that represents the number to number that is an integer.

Example: '123' -> 123

Few important things you need to pay attention to when writing the algorithm:

Check with interviewer if base is 10, otherwise for base 16, algorithm will need few adjustments
String is an array of ASCII characters
String might contain spaces, both at the beginning like at the end of the string
String might contain unknown characters (ex. 'a', 'z', 'n', where it is supposed to have only '0'-'9') - you need to either ignore this or break processing when you encounter specific 'not supported' character)
Number can be 0 or negative

When writing algorithm it is usually assumed that characters are ASCII characters. In this case characters that represent digits like '0', '1', '2', are consecutive characters, ex. ASCII value of '1' is just next to ASCII value of '1' and is exactly 1 more in value. This allows you to assume that you do not need to know explicit value of ASCII character '1', but you can convert it into value 1, by subtracting ASCII value of '1' from ASCII value of '0'. This is how algorithm is constructed.

Below are two different functions, first one - simple one that converts 'base 10' numbers; second - more complicated one that converts 'base 16' (hex) numbers

Complexity

Complexity is O(n).
Complexity of this algorithm is not so important for this solution.

Solution - atoi (base 10)

int atoi(const char *str)
{
    int result = 0;
    bool sign = false;

    // remove any spaces

    while (*str == ' ') str++;

    // check for sign
    if (*str == '+') str++;
    else if (*str == '-') { sign = true; str++; }

    // convert characters to number
    while (*str && *str >= '0' && *str <= '9') result = result*10 + (*str++ - '0');
    
    if (sign)
    {
        return -result;
    }

    return result;
}

Solution - atoiHex (base 16)

int atoiHex(const char *str)
{
    int result = 0;
    bool sign = false;

    // skip whitespaces at the beginning
    while (*str == ' ') { str++; }

    // check the sign (number can be signed)
    // and skip this sign character
    if (*str == '+') { str++; }
    else if (*str == '-') { sign = true; str++; }

    // repeat until we still have characters
    // this assumes string is null-terminated
    while (*str != '\0')
    {
        // multiple current result by 16 (hex is base 16)
        result *= 16;

        // check if character is a number
        if (*str >= '0' && *str <= '9')
        {
            result += *str - '0';
        }
        // check if this is 'A' - 'F'
        else if (*str >= 'A' && *str <= 'F')
        {
            // in this case treat 'A' as 10
            result += 10 + ( *str - 'A');
        }
        // character can be also lowercase 'a' - 'f'
        else if (*str >= 'a' && *str <= 'f')
        {
            result += 10 + (*str - 'a');
        }

        // move to next character
        str++;
    }

    // depending if number is signed, return result
    if (sign)
    { 
        return -result;
    }
    else
    {
        return result;
    }
}