Quick Overview

Parse signed integers in bases 2–36 with explicit syntax, negative-boundary handling, pre-arithmetic overflow checks, and deterministic error precedence.

Parse a Signed Integer in an Arbitrary Base

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a production-style conversion from a signed string to a 32-bit integer in a supplied base. Implement `parse_base_integer(text: string, base: int) -> string`. Return the canonical base-10 integer on success. Return `INVALID` for invalid syntax or an unsupported base, and `OVERFLOW` for a syntactically valid value outside signed 32-bit range. ### Constraints & Assumptions The source requests arbitrary-base atoi and explicitly notes the negative-number case. The following strict parsing and error policy is an explicit practice contract. - `2 <= base <= 36` is supported; any other base returns `INVALID`. - Input length is at most 100000 characters. Trim only ASCII spaces at the two ends. Internal whitespace, tabs, separators, and trailing non-digit text are invalid. No base prefix is specially recognized or stripped: all characters after the optional sign are interpreted by the digit grammar for the supplied base. Thus `0x1` is valid ordinary digits in base 36 (value 1189), but invalid in base 16 because `x` is not a base-16 digit. - After trimming, accept an optional single `+` or `-`, followed by at least one digit. Digits are `0`–`9`, `a`–`z`, or `A`–`Z`, with letters representing 10 through 35, case-insensitively. Every digit value must be less than base. - The signed range is -2147483648 through 2147483647. Leading zeroes are allowed. Both `-0` and `+0` return `0`. - Syntax takes precedence over overflow: if any character violates the grammar, return `INVALID` even if an earlier prefix already overflowed. Otherwise return `OVERFLOW` if the magnitude is too large. - Aim for O(length) time and O(1) auxiliary space. Do not depend on arbitrary-precision conversion of the whole input. ### Examples ```text parse_base_integer(" -80000000 ",16) -> "-2147483648" parse_base_integer("7fffffff",16) -> "2147483647" parse_base_integer("80000000",16) -> "OVERFLOW" parse_base_integer("10102",2) -> "INVALID" parse_base_integer("+000",10) -> "0" parse_base_integer("0x1",36) -> "1189" parse_base_integer("0x1",16) -> "INVALID" ``` Explain validation of empty/sign-only strings and how the negative boundary differs from the positive boundary. Describe how you detect overflow before multiplication and addition. ```hint Check against a sign-specific magnitude bound Before appending digit d to accumulated magnitude v, compare v with the largest value for which `v * base + d` remains allowed. Continue syntax validation after detecting overflow. ```

Overview: Parse signed integers in bases 2–36 with explicit syntax, negative-boundary handling, pre-arithmetic overflow checks, and deterministic error precedence.

Read the full Microsoft Software Engineer interview experience this question came from

Implement a production-style conversion from a signed string to a 32-bit integer in a supplied base. Implement `parse_base_integer(text: string, base: int) -> string`. Return the canonical base-10 integer on success. Return `INVALID` for invalid syntax or an unsupported base, and `OVERFLOW` for a syntactically valid value outside signed 32-bit range. ### Constraints & Assumptions The source requests arbitrary-base atoi and explicitly notes the negative-number case. The following strict parsing and error policy is an explicit practice contract. - `2 <= base <= 36` is supported; any other base returns `INVALID`. - Input length is at most 100000 characters. Trim only ASCII spaces at the two ends. Internal whitespace, tabs, separators, and trailing non-digit text are invalid. No base prefix is specially recognized or stripped: all characters after the optional sign are interpreted by the digit grammar for the supplied base. Thus `0x1` is valid ordinary digits in base 36 (value 1189), but invalid in base 16 because `x` is not a base-16 digit. - After trimming, accept an optional single `+` or `-`, followed by at least one digit. Digits are `0`–`9`, `a`–`z`, or `A`–`Z`, with letters representing 10 through 35, case-insensitively. Every digit value must be less than base. - The signed range is -2147483648 through 2147483647. Leading zeroes are allowed. Both `-0` and `+0` return `0`. - Syntax takes precedence over overflow: if any character violates the grammar, return `INVALID` even if an earlier prefix already overflowed. Otherwise return `OVERFLOW` if the magnitude is too large. - Aim for O(length) time and O(1) auxiliary space. Do not depend on arbitrary-precision conversion of the whole input. ### Examples ```text parse_base_integer(" -80000000 ",16) -> "-2147483648" parse_base_integer("7fffffff",16) -> "2147483647" parse_base_integer("80000000",16) -> "OVERFLOW" parse_base_integer("10102",2) -> "INVALID" parse_base_integer("+000",10) -> "0" parse_base_integer("0x1",36) -> "1189" parse_base_integer("0x1",16) -> "INVALID" ``` Explain validation of empty/sign-only strings and how the negative boundary differs from the positive boundary. Describe how you detect overflow before multiplication and addition. ```hint Check against a sign-specific magnitude bound Before appending digit d to accumulated magnitude v, compare v with the largest value for which `v * base + d` remains allowed. Continue syntax validation after detecting overflow. ```

Constraints

  • Input length is at most 100000; supported integer bases are 2 through 36, otherwise return INVALID.
  • Trim only ASCII spaces at both ends; accept one optional sign followed by at least one ASCII digit or letter with value below base.
  • No prefix stripping; internal whitespace, tabs, separators, other characters and trailing nondigit text are invalid.
  • Valid signed range is -2147483648 through 2147483647; leading zeroes are allowed and signed zero returns 0.
  • Syntax errors return INVALID before overflow handling; otherwise out-of-range values return OVERFLOW.
  • Success returns the canonical decimal integer string.

Examples

Input: (' -80000000 ', 16)

Expected Output: '-2147483648'

Explanation: The negative bound permits magnitude 2^31.

Input: ('0x1', 36)

Expected Output: '1189'

Explanation: x is digit 33 in base 36, not a prefix marker.

Loading coding console...

Show the approach

Approach

Validate the base, then locate the trimmed interval by advancing indices over ASCII space only. Consume at most one leading sign and require at least one following character. Decode each remaining character with explicit ASCII ranges, rejecting all other characters and digit values outside the base. Use magnitude bound 2147483648 for negative inputs and 2147483647 otherwise. Before incorporating digit d, require v <= floor((limit-d)/base); this is exactly the condition v*base+d <= limit and avoids overflow before multiplication. Once exceeded, keep an overflow flag and stop changing the bounded accumulator, but continue checking every later character. A syntax error therefore returns INVALID even after overflow. After complete validation, return OVERFLOW if flagged, or format the signed magnitude in decimal. Formatting zero naturally removes either sign. This invariant bounds arithmetic throughout and never relies on arbitrary-precision whole-input conversion. Indices and a fixed number of numeric variables give constant auxiliary state; C++ takes its argument by value, so its input copy is excluded from that analysis.

Time complexity:
O(n), where n is text length
Space complexity:
O(1) auxiliary space, excluding the C++ value-parameter input copy