String to Integer (atoi)

String to Integer (atoi)

What is this problem about?

The "String to Integer (atoi)" problem is a classic software engineering challenge that involves implementing a function to convert a string into a 32-bit signed integer. The function must follow specific rules: it should ignore leading whitespace, handle an optional plus or minus sign, read the digits until a non-digit character is encountered, and convert those digits into an integer. Additionally, it must handle integer overflow and underflow by clamping the result to the range [-2^31, 2^31 - 1]. It's a test of handling messy input and strict edge cases.

Why is this asked in interviews?

This is a staple question at companies like Apple, Uber, and Goldman Sachs because it mirrors real-world tasks where input data is often unformatted or potentially malicious. It tests a candidate's attention to detail, ability to handle edge cases, and understanding of numerical limits. While the logic is simple, there are many places to fail—such as missing a sign, failing on empty strings, or not handling overflow correctly. It's a "clean code" test as much as it is an algorithmic one.

Algorithmic pattern used

The pattern for this problem is simple Linear Scanning and State Management. You iterate through the string once, maintaining the current state (e.g., whether you are looking for a sign, reading digits, or done). Crucially, you must check for overflow before multiplying the current result by 10 and adding the new digit. This involves comparing the current total against the maximum integer divided by 10.

Example explanation (use your own example)

Let's process the input string " -42 words".

1. Skip the leading spaces. Now we are at "-42 words".
2. Check for a sign. We find '-', so our sign is negative.
3. Move to '4'. Convert '4' to integer 4. Current result: 4.
4. Move to '2'. Convert '2' to integer 2. Update result: 4 * 10 + 2 = 42.
5. Move to ' '. It's not a digit. Stop processing.
6. Apply the sign: -42.
7. Check if -42 is within [-2147483648, 2147483647]. It is. Final result: -42.

Common mistakes candidates make

The most common mistake is not handling integer overflow correctly. Many candidates wait until after the overflow occurs to check for it, which is too late in languages with fixed-size integers. Another mistake is failing to stop immediately when a non-digit character is encountered after the numbers have started. Some also forget to handle the case where the string contains only whitespace or a sign without any digits.

Interview preparation tip

When tackling the String to Integer (atoi) coding problem, focus on the order of checks. Always handle whitespace first, then the sign, then the digits. Use a long (if available) to store the intermediate result to make overflow checks easier, or perform the checks using division. Writing out a checklist of edge cases (empty string, overflow, leading zeros, invalid characters) before you start coding will demonstrate a structured approach to your interviewer.