Jobs

Interviews

Discussions

Strobogrammatic Number

Easy

Google

1 view

Topics:

StringsTwo Pointers

Given a string num representing an integer, determine if it is a strobogrammatic number. A strobogrammatic number is a number that looks the same when rotated 180 degrees (upside down). The valid pairs are (0, 0), (1, 1), (6, 9), (8, 8), and (9, 6). Can you provide an algorithm and code to check if a given number is strobogrammatic?

For example:

"69" is strobogrammatic because when rotated 180 degrees, it becomes "96".
"818" is strobogrammatic because when rotated 180 degrees, it remains "818".
"68" is not strobogrammatic because when rotated 180 degrees, it does not become a valid number.
"101" is strobogrammatic because when rotated 180 degrees, it remains "101".

Could you also discuss the time and space complexity of your solution, and handle potential edge cases like empty strings or null inputs? Also, how would you handle leading zeros, and how would your code behave when the number consists of only one digit like '0', '1', or '8'?

Strobogrammatic Number

Easy

Google

1 view

Topics:

StringsTwo Pointers

For example:

"69" is strobogrammatic because when rotated 180 degrees, it becomes "96".
"818" is strobogrammatic because when rotated 180 degrees, it remains "818".
"68" is not strobogrammatic because when rotated 180 degrees, it does not become a valid number.
"101" is strobogrammatic because when rotated 180 degrees, it remains "101".

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the input type? Is it a string representing a number or an integer?
What is the range of possible input values? Should I expect very large numbers?
Are leading zeros allowed in the input? For example, is "069" a valid strobogrammatic number?
Is the input guaranteed to be a non-negative number?
If the input is not a strobogrammatic number, what should I return? Should I throw an exception, return null, or return a boolean indicating false?

Brute Force Solution

Approach

The strobogrammatic number problem is about finding numbers that look the same when rotated 180 degrees. The brute force approach involves checking every possible number within the given length constraints to see if it is strobogrammatic.

Here's how the algorithm would work step-by-step:

Generate every possible number of the specified length.
For each generated number, check if it is strobogrammatic. This involves comparing digits from the beginning and end, moving towards the middle.
For each pair of digits, determine if they are strobogrammatic pairs (like 6 and 9, 0 and 0, 1 and 1, 8 and 8).
If any pair is not a valid strobogrammatic pair, then the number is not strobogrammatic.
If all digit pairs are valid, then the number is strobogrammatic, so keep track of it.
Continue checking all generated numbers. After checking every single number of the specified length, you will have found all strobogrammatic numbers within the length.

Code Implementation

def find_strobogrammatic_numbers(number_length):
    result = []

    def generate_numbers(current_number, length):
        if length == 0:
            if len(current_number) > 1 and current_number[0] == '0':
                return
            if len(current_number) > 0:
                if is_strobogrammatic(current_number):
                    result.append(current_number)
            return

        generate_numbers(current_number + '0', length - 1)
        generate_numbers(current_number + '1', length - 1)
        generate_numbers(current_number + '8', length - 1)
        generate_numbers(current_number + '6', length - 1)
        generate_numbers(current_number + '9', length - 1)

    def is_strobogrammatic(number):
        left_index = 0
        right_index = len(number) - 1

        #Compare numbers from outside in
        while left_index <= right_index:
            if number[left_index] == number[right_index]:
                if number[left_index] != '0' and number[left_index] != '1' and number[left_index] != '8':
                    return False
            elif (number[left_index] == '6' and number[right_index] == '9') or \
                 (number[left_index] == '9' and number[right_index] == '6'):
                pass
            else:
                return False

            left_index += 1
            right_index -= 1

        return True

    #Check to see if the number has any length at all.
    if number_length > 0:
        generate_numbers('', number_length)

    return result

Big(O) Analysis

Time Complexity

O(10^n * n) – The described brute force approach involves generating all possible numbers of length n. Since each digit can be one of 10 values (0-9), there are 10^n possible numbers. For each of these 10^n numbers, we need to check if it is strobogrammatic, which involves comparing digits from the beginning and end of the number towards the middle. This comparison takes O(n) time, as we iterate through at most n/2 pairs of digits. Therefore, the overall time complexity is O(10^n * n).

Space Complexity

O(N) – The brute force approach first generates every possible number of length N. The algorithm then stores each generated number in memory before checking if it is strobogrammatic. Therefore, the space required to store these numbers grows linearly with the input length N, where N is the length of the numbers being generated and checked. This results in O(N) space complexity due to the storage of the generated numbers.

Optimal Solution

Approach

The trick to this problem is to compare the number from both ends simultaneously. We check to see if the digits match with their strobogrammatic counterpart while moving inwards, meaning comparing the outer digits first and then moving towards the center.

Here's how the algorithm would work step-by-step:

Picture the number as a sequence of digits.
Start by looking at the first digit and the last digit at the same time.
Check if they are strobogrammatic pairs. Strobogrammatic pairs are numbers that when rotated 180 degrees result in a valid number. For example, 0 and 0, 1 and 1, 6 and 9, and 8 and 8.
Move inwards by one position from both ends. Check if these new digits are also strobogrammatic pairs.
Keep moving inwards and comparing digits until you reach the middle of the number.
If, at any point, you find a pair of digits that are not strobogrammatic, you know the number is not strobogrammatic and can stop.
If you reach the middle of the number and all pairs have been strobogrammatic, then the number is strobogrammatic.

Code Implementation

def is_strobogrammatic(number):
    left_index = 0
    right_index = len(number) - 1

    while left_index <= right_index:
        left_digit = number[left_index]
        right_digit = number[right_index]

        # Checking for strobogrammatic pairs
        if (left_digit == '0' and right_digit == '0') or \
           (left_digit == '1' and right_digit == '1') or \
           (left_digit == '6' and right_digit == '9') or \
           (left_digit == '8' and right_digit == '8') or \
           (left_digit == '9' and right_digit == '6'):
            left_index += 1
            right_index -= 1

        else:
            # If no strobogrammatic pair is found
            return False

    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the number string by comparing characters from both ends towards the middle. The number of iterations is directly proportional to the number of digits 'n' in the input number. In each iteration, a constant amount of work is performed to check if the pair of digits are strobogrammatic. Therefore, the time complexity is linear with respect to the number of digits, resulting in O(n).

Space Complexity

O(1) – The algorithm's space complexity is O(1) because it uses a constant amount of extra memory. It only requires a few variables, such as loop indices or pointers, to compare digits from both ends of the input string. The amount of memory needed for these variables does not depend on the size of the input number (N), thus, the auxiliary space is constant.

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty list since there are no strobogrammatic numbers of length 0.
Input n = 0	Return an empty list as a strobogrammatic number cannot have length 0.
Input n = 1	Return the list ['0', '1', '8'] as these are the only single-digit strobogrammatic numbers.
Input n = 2	Return the list ['11', '69', '88', '96'] since these are the only two-digit strobogrammatic numbers (excluding '00').
Leading zero for n > 1 (e.g., '0x' is invalid)	When building longer numbers, ensure the first digit is not zero, unless n = 1.
Large input n, potentially leading to memory issues	The recursive/iterative solution should build the numbers incrementally to avoid excessive memory usage and a StackOverflow error during recursion for larger n
Odd length n with middle digit not 0, 1, or 8	For odd lengths, the middle digit MUST be 0, 1, or 8 to form a valid strobogrammatic number.
The final result list containing duplicate numbers	The recursive calls should avoid duplication while generating the numbers.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the input type? Is it a string representing a number or an integer?
What is the range of possible input values? Should I expect very large numbers?
Are leading zeros allowed in the input? For example, is "069" a valid strobogrammatic number?
Is the input guaranteed to be a non-negative number?
If the input is not a strobogrammatic number, what should I return? Should I throw an exception, return null, or return a boolean indicating false?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Generate every possible number of the specified length.
For each generated number, check if it is strobogrammatic. This involves comparing digits from the beginning and end, moving towards the middle.
For each pair of digits, determine if they are strobogrammatic pairs (like 6 and 9, 0 and 0, 1 and 1, 8 and 8).
If any pair is not a valid strobogrammatic pair, then the number is not strobogrammatic.
If all digit pairs are valid, then the number is strobogrammatic, so keep track of it.
Continue checking all generated numbers. After checking every single number of the specified length, you will have found all strobogrammatic numbers within the length.

Code Implementation

def find_strobogrammatic_numbers(number_length):
    result = []

    def generate_numbers(current_number, length):
        if length == 0:
            if len(current_number) > 1 and current_number[0] == '0':
                return
            if len(current_number) > 0:
                if is_strobogrammatic(current_number):
                    result.append(current_number)
            return

        generate_numbers(current_number + '0', length - 1)
        generate_numbers(current_number + '1', length - 1)
        generate_numbers(current_number + '8', length - 1)
        generate_numbers(current_number + '6', length - 1)
        generate_numbers(current_number + '9', length - 1)

    def is_strobogrammatic(number):
        left_index = 0
        right_index = len(number) - 1

        #Compare numbers from outside in
        while left_index <= right_index:
            if number[left_index] == number[right_index]:
                if number[left_index] != '0' and number[left_index] != '1' and number[left_index] != '8':
                    return False
            elif (number[left_index] == '6' and number[right_index] == '9') or \
                 (number[left_index] == '9' and number[right_index] == '6'):
                pass
            else:
                return False

            left_index += 1
            right_index -= 1

        return True

    #Check to see if the number has any length at all.
    if number_length > 0:
        generate_numbers('', number_length)

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Picture the number as a sequence of digits.
Start by looking at the first digit and the last digit at the same time.
Check if they are strobogrammatic pairs. Strobogrammatic pairs are numbers that when rotated 180 degrees result in a valid number. For example, 0 and 0, 1 and 1, 6 and 9, and 8 and 8.
Move inwards by one position from both ends. Check if these new digits are also strobogrammatic pairs.
Keep moving inwards and comparing digits until you reach the middle of the number.
If, at any point, you find a pair of digits that are not strobogrammatic, you know the number is not strobogrammatic and can stop.
If you reach the middle of the number and all pairs have been strobogrammatic, then the number is strobogrammatic.

Code Implementation

def is_strobogrammatic(number):
    left_index = 0
    right_index = len(number) - 1

    while left_index <= right_index:
        left_digit = number[left_index]
        right_digit = number[right_index]

        # Checking for strobogrammatic pairs
        if (left_digit == '0' and right_digit == '0') or \
           (left_digit == '1' and right_digit == '1') or \
           (left_digit == '6' and right_digit == '9') or \
           (left_digit == '8' and right_digit == '8') or \
           (left_digit == '9' and right_digit == '6'):
            left_index += 1
            right_index -= 1

        else:
            # If no strobogrammatic pair is found
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return an empty list since there are no strobogrammatic numbers of length 0.
Input n = 0	Return an empty list as a strobogrammatic number cannot have length 0.
Input n = 1	Return the list ['0', '1', '8'] as these are the only single-digit strobogrammatic numbers.
Input n = 2	Return the list ['11', '69', '88', '96'] since these are the only two-digit strobogrammatic numbers (excluding '00').
Leading zero for n > 1 (e.g., '0x' is invalid)	When building longer numbers, ensure the first digit is not zero, unless n = 1.
Large input n, potentially leading to memory issues	The recursive/iterative solution should build the numbers incrementally to avoid excessive memory usage and a StackOverflow error during recursion for larger n
Odd length n with middle digit not 0, 1, or 8	For odd lengths, the middle digit MUST be 0, 1, or 8 to form a valid strobogrammatic number.
The final result list containing duplicate numbers	The recursive calls should avoid duplication while generating the numbers.