String to Integer (atoi)
Asked at Databricks, Netflix
Problem
Implement the atoi function which converts a string to a 32-bit signed integer. It must handle leading whitespace, optional sign, non-numeric characters, and overflow. This problem tests careful step-by-step parsing.
Asked At
| Company | Difficulty | |
|---|---|---|
| Databricks | Medium | View all Databricks questions → |
| Netflix | Medium | View all Netflix questions → |
How to Think About It
Step 1: skip leading whitespace. Step 2: handle optional +/- sign. Step 3: read digits until a non-digit or end of string. Step 4: handle overflow by clamping to [-2^31, 2^31 - 1].
Overflow detection: before multiplying by 10 and adding the digit, check if the result would exceed INT_MAX or fall below INT_MIN. If so, clamp.
The sign can only appear once. If you encounter a sign character after already reading digits, stop parsing.
Visual walkthrough for " -42":
Skip whitespace. Sign = -1. Read digits: 4, 2.
Result = 42. Apply sign: -42. Within range. Return -42.
Visual walkthrough for "4193 with words":
Read digits: 4, 1, 9, 3. Hit space → stop.
Result = 4193. Within range. Return 4193.
Visual walkthrough for "words and 987":
First char is 'w' (not digit, not sign, not space) → return 0.
Edge cases: empty string (return 0), no digits (return 0), INT_MAX/INT_MIN overflow (clamp), leading zeros ("00042" → 42).
Optimal Approach
Step 1: Skip leading whitespace.
Step 2: Check for +/- sign. Set multiplier accordingly.
Step 3: Read digits, building the result: result = result * 10 + digit.
Step 4: After each digit, check for overflow:
If result > INT_MAX, return INT_MAX (positive) or INT_MIN (negative).
Step 5: Apply sign and return.
Overflow check formula: if result > (INT_MAX - digit) / 10, overflow will occur on next step.
Time: O(n) — single pass through the string. Space: O(1).
What Trips People Up in Real Interviews
Not handling leading whitespace. The atoi function skips all leading spaces before processing.
Allowing multiple sign characters. Only one +/- sign is allowed at the beginning. If a second sign appears, stop parsing.
Not detecting overflow. A 32-bit signed integer has range [-2^31, 2^31 - 1]. If the result exceeds this, clamp to the boundary.
Returning 0 for a string with no digits. If the string has no valid digits after optional sign, return 0.
Using built-in string-to-int conversion. The problem asks you to implement atoi yourself. Don't use parseInt or stoi.
Solution Code
def myAtoi(s):
i = 0
n = len(s)
while i < n and s[i] == ' ':
i += 1
if i == n:
return 0
sign = 1
if s[i] == '+' or s[i] == '-':
sign = -1 if s[i] == '-' else 1
i += 1
result = 0
while i < n and s[i].isdigit():
digit = int(s[i])
if result > (2**31 - 1 - digit) // 10:
return 2**31 - 1 if sign == 1 else -2**31
result = result * 10 + digit
i += 1
return sign * resultFrequently Asked Questions
What is the String to Integer (atoi) problem?
Implement the `atoi` function which converts a string to a 32-bit signed integer. It must handle leading whitespace, optional sign, non-numeric characters, and overflow. This problem tests careful step-by-step parsing.
How do you solve String to Integer (atoi)?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask String to Integer (atoi)?
String to Integer (atoi) is asked at Databricks, Netflix. It is a medium difficulty problem.
What are common mistakes on String to Integer (atoi)?
- Not handling leading whitespace. The `atoi` function skips all leading spaces before processing.
- Allowing multiple sign characters. Only one +/- sign is allowed at the beginning. If a second sign appears, stop parsing.
- Not detecting overflow. A 32-bit signed integer has range [-2^31, 2^31 - 1]. If the result exceeds this, clamp to the boundary.
- Returning 0 for a string with no digits. If the string has no valid digits after optional sign, return 0.
- Using built-in string-to-int conversion. The problem asks you to implement `atoi` yourself. Don't use `parseInt` or `stoi`.