Write a function to validate a string as a valid integer representation, handling signs and spaces. Interview Question for Netflix

Write a function that validates if a given string is a valid representation of an integer. The function should handle positive, negative, and zero values. It should also account for leading/trailing spaces, but return false if there are any non-numeric characters other than a single leading '+' or '-' sign.

Details:

The input is a string.
The output is a boolean: true if the string represents a valid integer, false otherwise.
A valid integer string can start with an optional '+' or '-' sign.
The rest of the string must contain only digits.
Leading and trailing whitespace should be ignored.
The string must not contain any other non-numeric characters.

Examples:

" +123 " should return true
"-456" should return true
"0" should return true
"+007" should return true
"abc" should return false
"12.3" should return false
"1a" should return false
" " should return false
"++12" should return false
"--12" should return false
"12+" should return false
"12-" should return false

Considerations:

Handle empty strings gracefully.
Be mindful of potential integer overflow issues (although the function does not need to explicitly check for it). Focus on validating the format of the string.
Ensure your solution efficiently handles various edge cases and invalid inputs.

Your function should demonstrate clear, concise, and well-documented code.

## Validating Integer Strings

This problem requires us to write a function that determines if a given string is a valid integer representation, considering positive, negative, and zero values, and handling leading/trailing spaces. It emphasizes attention to detail and validation rather than complex algorithms.

### Naive Approach

One straightforward approach is to first trim the string to remove leading and trailing spaces. Then, check if the string is empty. If not, check for an optional sign (+ or -) at the beginning. Finally, iterate through the remaining characters to ensure they are all digits.

```python
def is_valid_integer_naive(s):
    s = s.strip()
    if not s:
        return False

    sign = 1
    start = 0

    if s[0] == '+':
        start = 1
    elif s[0] == '-':
        start = 1
        sign = -1

    if start == len(s):
        return False

    for i in range(start, len(s)):
        if not s[i].isdigit():
            return False

    return True

Optimal Solution

Building upon the naive approach, the optimized solution aims to reduce redundancy and improve readability. It follows a similar logic but is structured for better clarity and conciseness.

def is_valid_integer(s):
    s = s.strip()
    if not s:
        return False

    n = len(s)
    start = 0

    if s[0] == '+' or s[0] == '-':
        start = 1
        if n == 1: # Only a sign
            return False

    for i in range(start, n):
        if not s[i].isdigit():
            return False

    return True

Big(O) Run-time Analysis

The dominant operation in both the naive and optimal solutions is iterating through the string to check if each character is a digit. In the worst-case scenario, the loop iterates through each character of the string once. Therefore, the run-time complexity is O(n), where n is the length of the string after trimming whitespace.

Big(O) Space Usage Analysis

The space complexity of both solutions is O(1) (constant). No additional data structures that scale with the input string's size are created. The s = s.strip() operation creates a new string, but its size is still bounded by the original input, and it doesn't represent additional space that scales with n. Temporary variables such as sign, start, and i take up constant space, regardless of the input size.

Edge Cases

Here are some edge cases and how the provided solution handles them:

Empty String: The function returns false if the input string is empty or becomes empty after trimming.
String with Only Whitespace: Similar to an empty string, the function returns false.
String with Only a Sign: Returns false if the string consists of only a '+' or '-' sign after trimming.
Multiple Signs: The function handles multiple leading signs incorrectly, returning false only if the first character is a '+' or '-'. A more robust solution would explicitly check for multiple signs.
Non-numeric Characters: The function returns false if any non-numeric characters (excluding the optional leading sign) are present in the string.
Leading Zeros: The function correctly handles leading zeros.
Integer Overflow: While the function validates the format, it does not explicitly check for integer overflow. This aspect was out of scope for this problem.
Invalid characters after number: e.g. "123a" - Returns false correctly

# Example Usage and Test Cases:

print(is_valid_integer("  +123  "))  # True
print(is_valid_integer("-456"))   # True
print(is_valid_integer("0"))     # True
print(is_valid_integer("+007"))  # True
print(is_valid_integer("abc"))   # False
print(is_valid_integer("12.3"))  # False
print(is_valid_integer("1a"))    # False
print(is_valid_integer(" "))     # False
print(is_valid_integer("++12"))  # False
print(is_valid_integer("--12"))  # False
print(is_valid_integer("12+"))   # False
print(is_valid_integer("12-"))   # False
print(is_valid_integer("   "))    # False
print(is_valid_integer("+"))     # False
print(is_valid_integer("-"))     # False
print(is_valid_integer("123a"))  # False