Jobs

Interviews

Discussions

Valid Phone Numbers

Easy

Asked by:

More companies

21 views

Topics:

Strings

Given a text file file.txt that contains a list of phone numbers (one per line), write a one-liner bash script to print all valid phone numbers.

You may assume that a valid phone number must appear in one of the following two formats: (xxx) xxx-xxxx or xxx-xxx-xxxx. (x means a digit)

You may also assume each line in the text file must not contain leading or trailing white spaces.

Example:

Assume that file.txt has the following content:

987-123-4567
123 456 7890
(123) 456-7890

Your script should output the following valid phone numbers:

987-123-4567
(123) 456-7890

Try coding it in LeetCode

Valid Phone Numbers

Easy

Asked by:

21 views

Topics:

Strings

Given a text file file.txt that contains a list of phone numbers (one per line), write a one-liner bash script to print all valid phone numbers.

You may assume that a valid phone number must appear in one of the following two formats: (xxx) xxx-xxxx or xxx-xxx-xxxx. (x means a digit)

You may also assume each line in the text file must not contain leading or trailing white spaces.

Example:

Assume that file.txt has the following content:

987-123-4567
123 456 7890
(123) 456-7890

Your script should output the following valid phone numbers:

987-123-4567
(123) 456-7890

Try coding it in LeetCode

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:

Can the `phoneNumbers` array be empty or contain null values?
Can any of the strings in `phoneNumbers` be null or empty strings?
Are all characters in the input strings guaranteed to be digits, parentheses, and hyphens, or could there be other characters?
Should I assume that the 'XXX' placeholders must be valid three-digit numbers (e.g., no leading zeros after the parenthesis)?
What should I return if a phone number almost matches the pattern but has, for example, too few or too many digits?

Brute Force Solution

Approach

The brute force method for finding valid phone numbers involves checking every possible combination of numbers to see if it matches the required phone number pattern. We essentially try out all the possibilities, one by one, until we find the ones that are valid.

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

Start by looking at the beginning of the input string.
Check if the very first part of the string could possibly be a valid phone number.
If it is, save this possible phone number and continue looking at the rest of the string to see if the remainder is also a valid phone number or can be broken down into more valid phone numbers.
If the first part wasn't a valid phone number, move ahead one number/character in the string and try again.
Keep doing this, sliding along the entire string, checking every possible starting point and length to see if a valid phone number can be formed.
Collect all the combinations that result in valid phone numbers covering the whole string.
Present all the valid phone numbers.

Code Implementation

def find_valid_phone_numbers_brute_force(input_string):
    valid_phone_numbers = []
    string_length = len(input_string)

    for start_index in range(string_length):
        for end_index in range(start_index + 1, string_length + 1):
            possible_phone_number = input_string[start_index:end_index]

            # Check if the current substring is a valid phone number
            if is_valid_phone_number(possible_phone_number):
                remaining_string = input_string[end_index:]

                # If the remaining string is empty, we have a valid phone number
                if not remaining_string:
                    valid_phone_numbers.append(possible_phone_number)
                else:

                    # Recursively check the rest of the string for more valid numbers
                    remaining_valid_numbers = find_valid_phone_numbers_brute_force(remaining_string)

                    # If the remaining string can be broken down into valid numbers, save
                    if remaining_valid_numbers:
                        for number in remaining_valid_numbers:
                            valid_phone_numbers.append(possible_phone_number + ' ' + number)
    return valid_phone_numbers

def is_valid_phone_number(phone_number):
    # Check if the number matches a simple phone number pattern
    phone_number = phone_number.replace('-', '').replace(' ', '')
    if len(phone_number) == 10 and phone_number.isdigit():
        return True
    elif len(phone_number) == 7 and phone_number.isdigit():
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(n^2) – The described brute force approach iterates through the input string of length n, considering each position as a potential starting point for a phone number. For each starting position, it checks all possible lengths of substrings to see if they form a valid phone number, leading to another loop that can iterate up to n times. Thus, the algorithm involves a nested loop structure where, in the worst-case scenario, the outer loop runs n times and the inner loop can also run up to n times. This results in approximately n * n comparisons, which simplifies to a time complexity of O(n^2).

Space Complexity

O(N^2) – The algorithm explores all possible substrings, checking each for phone number validity. This implies storing combinations of valid prefixes discovered so far. In the worst-case scenario, where a large number of prefixes are potentially valid, the storage for these combinations could grow quadratically with the input string length N, since for each starting position, we might store up to N possible lengths for valid prefixes. Thus, the auxiliary space is O(N^2) to store the intermediate results of valid prefixes and their combinations.

Optimal Solution

Approach

To efficiently determine if a list of strings are valid phone numbers, we'll focus on checking each string against a specific pattern rather than comparing every string to each other. We'll use a shortcut that quickly confirms if a string matches the required format, skipping any further checks if it does not.

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

Consider each string representing a potential phone number one at a time.
Define the rules for a valid phone number clearly. For example, it might need to be in the form (XXX) XXX-XXXX where X is a number.
For each string, check if it exactly matches the required pattern, paying close attention to the position of characters, dashes, parenthesis and the number of digits.
If a string follows the rules, confirm that the digits are numbers.
If a string fails to match the pattern, immediately mark it as invalid and move to the next string.
After checking all strings, report which ones are valid phone numbers based on matching the format.

Code Implementation

def valid_phone_numbers(phone_numbers):
    valid_numbers = []

    for phone_number in phone_numbers:
        # Check the phone number against the expected format.
        if len(phone_number) == 14 and \
           phone_number[0] == '(' and \
           phone_number[4] == ')' and \
           phone_number[5] == ' ' and \
           phone_number[9] == '-':

            is_valid = True
            # Validate each character within the number is a digit
            for i in range(1, 4):
                if not phone_number[i].isdigit():
                    is_valid = False
                    break
            for i in range(6, 9):
                if not phone_number[i].isdigit():
                    is_valid = False
                    break
            for i in range(10, 14):
                if not phone_number[i].isdigit():
                    is_valid = False
                    break

            if is_valid:
                valid_numbers.append(phone_number)

    return valid_numbers

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through each of the n phone number strings in the input list. For each phone number string, it performs a pattern matching operation, which takes m time, where m is the length of the phone number string. Therefore, the overall time complexity is proportional to the product of the number of phone number strings (n) and the length of the phone number string (m). Since m is typically small and bounded by a constant (e.g., the maximum length of a phone number), it can often be considered O(1), making the overall time complexity O(n), however to be precise and because the pattern matching is described we say O(n*m).

Space Complexity

O(1) – The provided plain English explanation describes checking each string individually against a predefined pattern. It doesn't mention creating any auxiliary data structures like lists, arrays, or hash maps to store intermediate results or track progress across multiple strings. The algorithm's space usage is therefore dominated by a fixed number of variables to hold temporary values during pattern matching, such as a few boolean flags or indices within a string. Thus, the space complexity remains constant, irrespective of the number of input strings (N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty boolean array to indicate no phone numbers to validate.
Phone number strings with length less than 10 or greater than 14	Return false for these numbers immediately as they cannot match the required format.
Phone number strings with non-digit characters in the digit positions	The validation logic should check each character is a digit in the correct position, returning false otherwise.
Phone number strings with incorrect delimiters (e.g., using '[' instead of '(')	The validation logic should strictly check for the presence and correct placement of '(', ')', and '-'.
Very large input array with many phone numbers	The solution's time complexity should be O(N) where N is the number of phone numbers, avoiding quadratic or worse performance.
Phone number strings with leading or trailing whitespace	Trim the whitespace from the phone number string before validation, ensuring accurate matching.
Array contains phone numbers that are close to valid but have minor deviations (e.g. (123)1234-567 or (123) 123-4567)	The validation must strictly enforce the 'XXX) XXX-XXXX' format, returning false if deviations are found.
Phone numbers where all digits are same (e.g. (111) 111-1111)	The validation should not have any special treatment for these cases; it should validate the format regardless of the digits' values.

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:

Can the `phoneNumbers` array be empty or contain null values?
Can any of the strings in `phoneNumbers` be null or empty strings?
Are all characters in the input strings guaranteed to be digits, parentheses, and hyphens, or could there be other characters?
Should I assume that the 'XXX' placeholders must be valid three-digit numbers (e.g., no leading zeros after the parenthesis)?
What should I return if a phone number almost matches the pattern but has, for example, too few or too many digits?

Brute Force Solution

Approach

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

Start by looking at the beginning of the input string.
Check if the very first part of the string could possibly be a valid phone number.
If it is, save this possible phone number and continue looking at the rest of the string to see if the remainder is also a valid phone number or can be broken down into more valid phone numbers.
If the first part wasn't a valid phone number, move ahead one number/character in the string and try again.
Keep doing this, sliding along the entire string, checking every possible starting point and length to see if a valid phone number can be formed.
Collect all the combinations that result in valid phone numbers covering the whole string.
Present all the valid phone numbers.

Code Implementation

def find_valid_phone_numbers_brute_force(input_string):
    valid_phone_numbers = []
    string_length = len(input_string)

    for start_index in range(string_length):
        for end_index in range(start_index + 1, string_length + 1):
            possible_phone_number = input_string[start_index:end_index]

            # Check if the current substring is a valid phone number
            if is_valid_phone_number(possible_phone_number):
                remaining_string = input_string[end_index:]

                # If the remaining string is empty, we have a valid phone number
                if not remaining_string:
                    valid_phone_numbers.append(possible_phone_number)
                else:

                    # Recursively check the rest of the string for more valid numbers
                    remaining_valid_numbers = find_valid_phone_numbers_brute_force(remaining_string)

                    # If the remaining string can be broken down into valid numbers, save
                    if remaining_valid_numbers:
                        for number in remaining_valid_numbers:
                            valid_phone_numbers.append(possible_phone_number + ' ' + number)
    return valid_phone_numbers

def is_valid_phone_number(phone_number):
    # Check if the number matches a simple phone number pattern
    phone_number = phone_number.replace('-', '').replace(' ', '')
    if len(phone_number) == 10 and phone_number.isdigit():
        return True
    elif len(phone_number) == 7 and phone_number.isdigit():
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Consider each string representing a potential phone number one at a time.
Define the rules for a valid phone number clearly. For example, it might need to be in the form (XXX) XXX-XXXX where X is a number.
For each string, check if it exactly matches the required pattern, paying close attention to the position of characters, dashes, parenthesis and the number of digits.
If a string follows the rules, confirm that the digits are numbers.
If a string fails to match the pattern, immediately mark it as invalid and move to the next string.
After checking all strings, report which ones are valid phone numbers based on matching the format.

Code Implementation

def valid_phone_numbers(phone_numbers):
    valid_numbers = []

    for phone_number in phone_numbers:
        # Check the phone number against the expected format.
        if len(phone_number) == 14 and \
           phone_number[0] == '(' and \
           phone_number[4] == ')' and \
           phone_number[5] == ' ' and \
           phone_number[9] == '-':

            is_valid = True
            # Validate each character within the number is a digit
            for i in range(1, 4):
                if not phone_number[i].isdigit():
                    is_valid = False
                    break
            for i in range(6, 9):
                if not phone_number[i].isdigit():
                    is_valid = False
                    break
            for i in range(10, 14):
                if not phone_number[i].isdigit():
                    is_valid = False
                    break

            if is_valid:
                valid_numbers.append(phone_number)

    return valid_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty boolean array to indicate no phone numbers to validate.
Phone number strings with length less than 10 or greater than 14	Return false for these numbers immediately as they cannot match the required format.
Phone number strings with non-digit characters in the digit positions	The validation logic should check each character is a digit in the correct position, returning false otherwise.
Phone number strings with incorrect delimiters (e.g., using '[' instead of '(')	The validation logic should strictly check for the presence and correct placement of '(', ')', and '-'.
Very large input array with many phone numbers	The solution's time complexity should be O(N) where N is the number of phone numbers, avoiding quadratic or worse performance.
Phone number strings with leading or trailing whitespace	Trim the whitespace from the phone number string before validation, ensuring accurate matching.
Array contains phone numbers that are close to valid but have minor deviations (e.g. (123)1234-567 or (123) 123-4567)	The validation must strictly enforce the 'XXX) XXX-XXXX' format, returning false if deviations are found.
Phone numbers where all digits are same (e.g. (111) 111-1111)	The validation should not have any special treatment for these cases; it should validate the format regardless of the digits' values.