Coding Problem Interview Series: How to Convert a String to Integer (atoi())?

📣 Calling experienced devs and recent interviewees! Join the "Coding Problem Interview Series" to help code newbies tackle interview questions assessing problem-solving skills, algorithmic knowledge, and implementation of sorting, string manipulation, and data structure algorithms.

Share your expertise and insights! Pleas share multiple perspectives and tips for standout answers!

Today's question is:

In an interview setting, how would you approach converting a String to an integer (similar to the atoi() function)?

Follow the CodeNewbie Org and #codenewbie for more discussions and online camaraderie!

CodeNewbie Follow

CodeNewbie is the most supportive community of programmers, especially targeted towards people learning to code. Part of the DEV Family.

Comments

[lionel-rowe]

Troll answer (JS):

const atoi = parseInt

I think this needs a few self-imposed rules, such as not using any built-in language features or APIs to do the conversion.

function atoi(str) {
    // match 0-1 signs (+ or -), followed by 1 or more ASCII digits
    // formats like "1", "01", "+1", "-1" are allowed
    // formats like "0xff", "1e6", "1.1", " 1 " are rejected
    const matched = str.match(/^([+\-]?)(\d+)$/)

    // `matched` will be `null` if the format requirement wasn't met,
    // so we return Not a Number
    if (!matched) return NaN

    // destructure the capture groups: 0 is discarded (full match)
    const [, sign, digits] = matched

    let total = 0
    // go through the decimal places in reverse:
    // units, tens, hundreds, etc.
    for (const [i, digit] of [...digits].reverse().entries()) {
        // subtract 0x30 from the codepoint, as ASCII digits are
        // located at codepoints 0x30..0x39
        // (i.e. "0" is codepoint 0x30, "1" is 0x31, etc.)
        // multiply by 10 raised to the power of the appropriate
        // decimal place
        total += (digit.codePointAt(0) - 0x30) * 10 ** i
    }

    // multiply by -1 if the sign was negative
    return total * (sign === '-' ? -1 : 1)
}

atoi('42') // 42
atoi('-99') // -99
atoi('+500') // 500
atoi('0001230') // 1230
atoi('1.5') // NaN

[Uriel Bitton]

lol. let me do all your work in a single line:

function atoi(str) {
return +str
}

[lionel-rowe]

@urielbitton I still prefer my one-liner const atoi = parseInt, because +str doesn't fulfil the spec (might return a non-integer) 😉

[Santiago G. Marín]

True, +'...' behaves similar to Number, so it'll convert floats as well.

[Uriel Bitton]

@lionelrowe + quite literally replaces parseInt in 99% or perhaps 100% of cases in javascript.

[Santiago G. Marín]

Not if you only want integers...

[lionel-rowe]

@urielbitton It depends what your use case is. I usually use Number(str) instead of +str as it's more explicit, plus it can be passed as a callback to array functions (['1', '2', '3'].map(Number) => [1, 2, 3]). I usually only use parseInt if I want to parse in a radix other than 10, e.g. parsing hex strings (parseInt('ff', 16) => 255), or if I want the result to be truncated (parseInt('16.9')
=> 16). And I use parseFloat where I want to ignore a unit at the end, e.g. parseFloat('99.9%') => 99.9.

[Uriel Bitton]

just add .toFixed(0)

[Uriel Bitton]

just add .toFixed(0) ...

[lionel-rowe]

OK, that potentially covers 1 of the 4 use cases I mentioned, but it doesn't even work, as toFixed converts it back to a string...

function doNothing(numStr) {
    const num = +numStr
    const fixed = num.toFixed(0)

    return fixed
}

const numStr = '1'
typeof doNothing(numStr) // 'string'
doNothing(numStr) === numStr // true

Sure, you could re-convert to a number, but at that point you're degrading performance and complicating your code just to avoid using parseInt, a function that already exists natively in the language for that specific purpose.

[Han Mai]

The second answer is somehow same idea with the first answer but then the first one is much cleaner and more efficient in any ways. Solution they are looking for is maybe to parse manually, taking care of the cases, char to integer… very basic.

[Mike Stemle]

int atoi_func(const char* str, size_t len) {
  int aggregator = 0;
  char *ptr = str;

  while (*ptr != '\0' && (ptr - str) < len) {
    int digit = *ptr - '0';
    if (digit > 9 || digit < 0) {
      fprintf(stderr, "«%c» is not a digit.\n", *ptr);
      return -1;
    }

    aggregator += digit * (ptr - str);
  }

  if (*ptr != '\0') {
    fprintf(stderr, "potential overflow detected; no null terminator.\n");
    return -1;
  }

  return aggregator;
}

This was really hard to type in an iPhone, but I am pretty sure this is good, and that it covers the most common foot-guns.

[lionel-rowe]

Nice! Needs a couple of changes though — the math isn't quite right for summing the digits, and the while loop doesn't terminate as ptr is never incremented:

+ #include <math.h>

-    aggregator += digit * (ptr - str);
+    aggregator += digit * pow(10, len - (ptr - str) - 1);
+    ++ptr;

[Mike Stemle]

Thanks! I knew there was no way I nailed it first go on my iPhone.

[lionel-rowe]

Rust (be gentle, I'm learning 😅)

use std::error::Error;
use std::fmt;

#[derive(Debug)]
pub enum AtoiError {
    IntegerOverflow,
    ZeroLengthInput,
    InvalidChar(char),
}

impl fmt::Display for AtoiError {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:?}", self)
    }
}

impl Error for AtoiError {}

pub fn atoi(input: &str) -> Result<i64, AtoiError> {
    use crate::AtoiError::*;

    let mut chars = input.chars();

    // `sign` can be either `Some('+')`, `Some('-')`, or `None`
    let sign = match chars.next() {
        x @ Some('-' | '+') => x,
        Some(_) => None,
        None => return Err(ZeroLengthInput),
    };

    // `chars` iterator is currently at index 1 due to calling `next`
    // in previous expression.
    // If the sign wasn't explicitly specified, then re-start chars
    // iterator from index 0
    if sign.is_none() {
        chars = input.chars();
    }

    let mut total: i64 = 0;

    // Go through the decimal places in reverse:
    // units, tens, hundreds, etc.
    for (i, c) in chars.rev().enumerate() {
        match c {
            // Check if char is a digit
            c if c >= '0' && c <= '9' => {
                // Subtract codepoint of '0' from the char.
                // Multiply by 10 raised to the power of the appropriate
                // decimal place

                total = total
                    .checked_add(
                        (c as i64 - '0' as i64)
                            .checked_mul(10i64.checked_pow(i as u32).ok_or(IntegerOverflow)?)
                            .ok_or(IntegerOverflow)?,
                    )
                    .ok_or(IntegerOverflow)?;
            }
            // Return error result if char is not a digit
            c => return Err(InvalidChar(c)),
        };
    }

    // Multiply by -1 if the sign was negative
    Ok(match sign {
        Some('-') => total * -1,
        _ => total,
    })
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::AtoiError::*;

    #[test]
    fn valid() {
        assert!(matches!(atoi("0"), Ok(0)));
        assert!(matches!(atoi("42"), Ok(42)));
        assert!(matches!(atoi("-99"), Ok(-99)));
        assert!(matches!(atoi("+500"), Ok(500)));
        assert!(matches!(atoi("0001230"), Ok(1230)));
    }

    #[test]
    fn invalid() {
        assert!(matches!(atoi(""), Err(ZeroLengthInput)));
        assert!(matches!(atoi("1.5"), Err(InvalidChar('.'))));
        assert!(matches!(atoi("1-2"), Err(InvalidChar('-'))));
        assert!(matches!(atoi("1+3"), Err(InvalidChar('+'))));
        assert!(matches!(atoi("999999999999999999999"), Err(IntegerOverflow)));
    }
}

[Joan Llenas Masó]

Elm + Parser combinators:

You begin with the Integer data structure.

The intP parser is a recipe of how you can generate an Integer instance from a raw string, step by step.

Once you have filled all the holes of the data structure, you can then process it and generate the integer value (with the applySign function).

The atoi function wraps the execution of the parser and returns the Maybe Int value.

import Parser as P exposing ((|.), (|=), Parser)


type Sign
    = Positive
    | Negative


type Integer
    = Integer Sign String


applySign : Integer -> Maybe Int
applySign (Integer sign digits) =
    case ( sign, String.toInt digits ) of
        ( Positive, Just n ) ->
            Just n

        ( Negative, Just n ) ->
            Just (-1 * n)

        _ ->
            Nothing


intP : Parser Int
intP =
    P.succeed Integer
        |= P.oneOf
            [ P.symbol "+" |> P.map (always Positive)
            , P.symbol "-" |> P.map (always Negative)
            , P.succeed Positive
            ]
        |= (P.chompWhile Char.isDigit |> P.getChompedString)
        |. P.end
        |> P.andThen
            (\integer ->
                case applySign integer of
                    Just n ->
                        P.succeed n

                    Nothing ->
                        P.problem "applySign failed"
            )


atoi : String -> Maybe Int
atoi input =
    P.run intP input |> Result.toMaybe

atoi "1" -- Just 1
atoi "45" -- Just 45
atoi "-45" -- Just -45
atoi "" -- Nothing
atoi "--335" -- Nothing
atoi "-3-42" -- Nothing

This approach is closer to intermediate/advanced than to newbies, but this is how parsing is done in a functional style.

If you want to play with the exercise: ellie-app.com/nm6g8LCw37za1

[lionel-rowe]

I love reading Elm code even though I find it hard to understand, it's kinda brain-bending in a good way!

I noticed you're using String.toInt though, so you could replace the whole atoi implementation with that, as it already handles + and -:

module Main exposing (main)
import Html exposing (Html)

atoi = String.toInt

parse : String -> Html msg
parse s =
    atoi s
        |> Maybe.map String.fromInt
        |> Maybe.withDefault ("'" ++ s ++ "' is not a number")
        |> (\res -> Html.li [] [ Html.text res ])

main =
    Html.ul [] (List.map parse [ "0", "1", "45", "-45", "", "--335", "3abc" ])

[Joan Llenas Masó]

You are absolutely right! String.toInt already does the job. Wouldn't that be considered cheating during a job interview, though? :)

Parser combinators are an extra brain-bending feature within the language. But it is so powerful that it's worth learning if you want to parse stuff and RegEx falls too short for the job.

[logically-nerd]

JAVA
(still learning, so forgive my not so neat code😅)

class Solution {
    public int myAtoi(String s) {
        double num = 0;
        boolean neg=false,numFound=false,space=false;
        int charCount=0;
        for (char ch : s.toCharArray()) {
            if(charCount>=2){
                break;
            }
            if(charCount>0 && space){
                break;
            }
            if (ch >= '0' && ch <= '9') {
                numFound=true;
                num = ((int) ch - 48) + num * 10;
            }
            else if(!numFound&&ch=='-'){
                space=false;
                neg=true;
                charCount++;
            }
            else if(!numFound&&ch=='+'){
                space=false;
                charCount++;
            }
            else if(!numFound&&ch==' '){
                space=true;
                continue;
            }
            else if(!numFound&&ch=='.'){
                break;
            }
            else{
                break;
            }
        }
        if(neg)
            return (int)(0-num);
        return (int)num;
    }
}

[lionel-rowe]

Works perfectly, at least for well-formed input. For malformed input, Solution#.myAtoi('abc123') gives 0, and Solution#.myAtoi('123abc') gives 123, which is a reasonable thing to do if you want parsing to be lenient (JS's parseInt works similarly, except it returns NaN instead of 0 where the input begins with an unparseable char).

I don't think it makes much sense to have num be a double and then cast it to an int when returning it, though. To improve performance if nothing else, it'd be better to declare it as an int, then you can remove all the type casts.

The only possible drawback is that it changes the behavior for values that overflow the max int value: with purely int types, you get wrapping (2147483647 + 1 = -2147483648), whereas if using a double internally, you get saturation (2147483647 + 1 = 2147483647). I don't think either one is strictly more/less correct than the other, though.

[logically-nerd]

Hey lionel,
I just copied the copied that I wrote for the same questions in leetcode.😅
My code is logically designed based on its demand and test cases.

[Vladas Saulis]

var s = "2345";
var result = 1*s;

[Joan Llenas Masó]

Works most of the time, but there are a few edge cases:
"", " " are invalid inputs yet they return 0

[Vladas Saulis]

There is a lot of invalid inputs ("aaa", "baa", etc). You must know what you do.
But "" and " " are VALID inputs, because it returns valid answer - 0.

[Joan Llenas Masó]

Hey Vladas, sorry I wasn't clear enough in my response.
Let me illustrate my point:

1 * "3" // 3 <-- correct
1 * "a" // NaN <-- correct
1 * "" // 0 <-- incorrect, should have been NaN
1 * " " // 0 <-- incorrect, should have been NaN

Cheers!

[Vladas Saulis]

It must be an internal parser which just skips initial blanks, and it's initialized to 0.
I would program exactly the same.

[Tristan M・ﾄリスタン]

JS / TS Shorthand I only discovered more recently than I'm willing to admit

const stringNum = "12345"
const intNum = +stringNum

[Mike Stemle]

Perl had something that some referred to as the Venus operator, 0+. Very clever stuff.

[Nashe Omirro]

npm i atoi-js