A while ago I had an interesting interview question with a big tech company. The question was straight forward: Implement atoi() to convert a string to int.
Some restrictions apply:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned.
Note:
- Only the space character
' 'is considered as whitespace character. - Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.
Solution:
The way to handle this problem is to ignore all the restrictions at first. Think about how to implement atoi in a perfect world. This is pretty simple:
you would want to look at ASCII table. At each c
- Look at ASCII table and define the starting value of ‘0’ (this is 48)
- Subtract 48 from each ascii value of each character
- add them together and return the new int
An example: “123” str[0] = ‘1’; str[1] = ‘2’; str[2] = ‘3’
So if we get the ASCII value of ‘1’ which is 49 and we subtract 48 from it we end up with 1 the int value. Remember this is 100 and not just one in our final number; so a quick implementation would be:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
int myatoi(string str) { size_t size = str.size() - 1; int sum = 0; for (int i = 0; i <= size; ++i) { sum = sum + (str[i] - '0') * pow(10, size - i); } return sum; } |
Now this is all nice an easy, but now think how you will handle all the other monster values such as negative sign; positive sign, white spaces, illegal characters, empty strings, etc…
Here is my code for this problem:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
int myAtoi(string str) { if (str.size() == 0) return 0; double sum = 0; int size = str.size() - 1; int i = 0; short sign = 2; bool proc = false; for (i; i <= size; ++i) { if ((str[i] == ' ' || str[i] == '-' || str[i] == '+') && sum == 0 && sign == 2 && !proc) { if (str[i] != ' ') sign = (str[i] == '-') ? -1 : 1; continue; } else if ((str[i] < 48 || str[i] > 57) && sum > 0) { sum = sum / pow(10, size - i + 1); break; } else if ((str[i] < 48 || str[i] > 57) && sum == 0) return 0; sum = sum + (str[i] - '0') * pow(10, size - i); proc = true; } if (sign < 2) sum = sign * sum; if (sum > INT_MAX) sum = INT_MAX; else if (sum < INT_MIN) sum = INT_MIN; return sum; } |
Leave a reply