Jobs

Interviews

Discussions

Basic Calculator II

Medium

Uber

2 views

Topics:

StringsStacks

Given a string s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2^31, 2^31 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

For example:

s = "3+2*2" should return 7
s = " 3/2 " should return 1
s = " 3+5 / 2 " should return 5

Write a function to implement this. Consider the constraints:

1 <= s.length <= 3 * 10^5
s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
s represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, 2^31 - 1].
The answer is guaranteed to fit in a 32-bit integer.

Basic Calculator II

Medium

Uber

2 views

Topics:

StringsStacks

Given a string s which represents an expression, evaluate this expression and return its value. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2^31, 2^31 - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

For example:

s = "3+2*2" should return 7
s = " 3/2 " should return 1
s = " 3+5 / 2 " should return 5

Write a function to implement this. Consider the constraints:

1 <= s.length <= 3 * 10^5
s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
s represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, 2^31 - 1].
The answer is guaranteed to fit in a 32-bit integer.

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 range of values for the numbers in the input string, and are negative numbers allowed?
Besides '+', '-', '*', and '/', are there any other operators or special characters I should expect in the input string?
How should I handle division by zero; is it possible, and if so, what should the result be (e.g., throw an error, return 0, etc.)?
Can there be leading or trailing whitespace in the input string, or whitespace between numbers and operators, and how should I handle it?
If the expression is invalid (e.g., two operators in a row), should I return a specific error code/message, or can I assume the input will always be a valid expression according to the given operators?

Brute Force Solution

Approach

The brute force approach for evaluating a simple expression like '3+2*2' means we don't use any clever tricks. Instead, we explore all possible interpretations of the expression, even the wrong ones, until we find the correct answer. We treat everything like plain text and try every possibility.

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

First, we scan the entire expression from left to right.
Every time we encounter a number or an operation, we consider it as a standalone expression and see what happens if we immediately try to calculate something.
We might try to evaluate operations in the wrong order initially (e.g., adding before multiplying).
We keep track of all the intermediate results we get from these incorrect and correct orderings.
Eventually, by trying all combinations, we will get the correct result by processing the multiplication and division before addition and subtraction, even if we explored lots of other incorrect paths along the way.
Since we tracked all the intermediate results, we just need to select the one where calculations were eventually performed with the correct precedence to find the correct final answer.

Code Implementation

def basic_calculator_ii_brute_force(expression):
    results = []
    current_number = 0
    current_result = 0
    operation = '+'

    def evaluate(number_to_consider, current_operation):
        nonlocal current_result
        if current_operation == '+':
            current_result += number_to_consider
        elif current_operation == '-':
            current_result -= number_to_consider
        elif current_operation == '*':
            current_result *= number_to_consider
        elif current_operation == '/':
            # Integer division as specified in the prompt
            current_result = int(current_result / number_to_consider)

    for character in expression:
        if character.isdigit():
            current_number = current_number * 10 + int(character)
        elif character in '+-*/':
            # Evaluate the previous operation with the current number
            evaluate(current_number, operation)
            results.append(current_result)
            current_number = 0
            operation = character
        elif character == ' ':
            pass

    # Evaluate the last operation with the last number
    evaluate(current_number, operation)
    results.append(current_result)

    # Return the last result after all calculations
    # This implicitly tries all combinations
    return results[-1]

Big(O) Analysis

Time Complexity

O(n!) – The brute force approach, as described, explores all possible interpretations of the expression, essentially trying all permutations of operations. In the worst case, for an expression with n numbers and n-1 operators, the algorithm could potentially evaluate all possible orderings of these operations. The number of such orderings grows factorially with the number of operators (n-1), which is directly related to n. Therefore, the time complexity is O(n!).

Space Complexity

O(N^K) – The brute force approach, as described, explores all possible interpretations of the expression. This implies the algorithm maintains a record of intermediate results for all possible operator precedence combinations. In the worst case, for an expression of length N, there could be on the order of N operators. Assuming K represents the number of possible orderings/combinations which could be related to the number of operators, the number of intermediate results tracked could grow to be on the order of N raised to the power of K. Therefore, the space complexity would be O(N^K), where N is the length of the expression and K represents the number of different operator ordering possibilities explored.

Optimal Solution

Approach

The optimal approach avoids treating multiplication and division the same as addition and subtraction. Instead, we tackle the higher-priority math first, then the rest. This simplifies the calculation to a series of simple additions and subtractions.

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

Go through the entire expression from left to right.
When you encounter a multiplication or division, perform that operation immediately using the numbers right before and after it.
Replace the multiplication or division and the two numbers with the result of the calculation.
After finishing this first pass, you should now only have additions and subtractions left.
Now, go through the simplified expression from left to right, performing the additions and subtractions in order.
The final result of this second pass is the answer.

Code Implementation

def calculate(expression):
    current_number = 0
    stack_of_numbers = []
    last_operation = '+'

    for i, character in enumerate(expression):
        if character.isdigit():
            current_number = (current_number * 10) + int(character)
        if character in '+-*/' or i == len(expression) - 1:
            # Evaluate high-precedence operations immediately.
            if last_operation == '+':
                stack_of_numbers.append(current_number)
            elif last_operation == '-':
                stack_of_numbers.append(-current_number)
            elif last_operation == '*':
                stack_of_numbers.append(stack_of_numbers.pop() * current_number)
            else:
                stack_of_numbers.append(int(stack_of_numbers.pop() / current_number))
            last_operation = character
            current_number = 0

    # Sum remaining values in stack now, only additions and subtractions remain.
    result = 0

    for number in stack_of_numbers:
        result += number

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves two passes through the input string of length n. The first pass identifies and performs all multiplications and divisions. The second pass then performs the remaining additions and subtractions. Each pass iterates through the string once, performing a constant amount of work at each character. Therefore, the time complexity is proportional to n, which simplifies to O(n).

Space Complexity

O(N) – The described approach involves replacing multiplication and division operations and their operands with the result of the calculation. This implies that a new string or list of numbers and operators, at most the same length as the input string, would be created to hold these intermediate values. The first pass might reduce the length of the string, but in the worst-case scenario where there are no multiplications or divisions, the auxiliary storage will be the size of the original expression. Therefore, the auxiliary space complexity is O(N), where N is the length of the input expression.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 immediately as there is no expression to evaluate.
Input string with only whitespace	Return 0 since no valid expression is present.
Input string with leading/trailing whitespace	Trim the input string to remove any leading/trailing whitespace before processing.
Consecutive operators (e.g., 3 + - 2)	Handle the sign of the second operator by correctly parsing and applying to the subsequent number.
Division by zero	Return 0, or throw an exception, depending on the specific requirements.
Integer overflow during calculation	Use a larger integer type (e.g., long) or check for overflow before performing the calculation.
Input string with invalid characters (e.g., letters)	Return 0, throw an exception, or filter out invalid characters before processing.
Large numbers and number of operations	The stack based approach will scale to larger inputs and the integer type (int/long) choice affects range.

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 range of values for the numbers in the input string, and are negative numbers allowed?
Besides '+', '-', '*', and '/', are there any other operators or special characters I should expect in the input string?
How should I handle division by zero; is it possible, and if so, what should the result be (e.g., throw an error, return 0, etc.)?
Can there be leading or trailing whitespace in the input string, or whitespace between numbers and operators, and how should I handle it?
If the expression is invalid (e.g., two operators in a row), should I return a specific error code/message, or can I assume the input will always be a valid expression according to the given operators?

Brute Force Solution

Approach

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

First, we scan the entire expression from left to right.
Every time we encounter a number or an operation, we consider it as a standalone expression and see what happens if we immediately try to calculate something.
We might try to evaluate operations in the wrong order initially (e.g., adding before multiplying).
We keep track of all the intermediate results we get from these incorrect and correct orderings.
Eventually, by trying all combinations, we will get the correct result by processing the multiplication and division before addition and subtraction, even if we explored lots of other incorrect paths along the way.
Since we tracked all the intermediate results, we just need to select the one where calculations were eventually performed with the correct precedence to find the correct final answer.

Code Implementation

def basic_calculator_ii_brute_force(expression):
    results = []
    current_number = 0
    current_result = 0
    operation = '+'

    def evaluate(number_to_consider, current_operation):
        nonlocal current_result
        if current_operation == '+':
            current_result += number_to_consider
        elif current_operation == '-':
            current_result -= number_to_consider
        elif current_operation == '*':
            current_result *= number_to_consider
        elif current_operation == '/':
            # Integer division as specified in the prompt
            current_result = int(current_result / number_to_consider)

    for character in expression:
        if character.isdigit():
            current_number = current_number * 10 + int(character)
        elif character in '+-*/':
            # Evaluate the previous operation with the current number
            evaluate(current_number, operation)
            results.append(current_result)
            current_number = 0
            operation = character
        elif character == ' ':
            pass

    # Evaluate the last operation with the last number
    evaluate(current_number, operation)
    results.append(current_result)

    # Return the last result after all calculations
    # This implicitly tries all combinations
    return results[-1]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Go through the entire expression from left to right.
When you encounter a multiplication or division, perform that operation immediately using the numbers right before and after it.
Replace the multiplication or division and the two numbers with the result of the calculation.
After finishing this first pass, you should now only have additions and subtractions left.
Now, go through the simplified expression from left to right, performing the additions and subtractions in order.
The final result of this second pass is the answer.

Code Implementation

def calculate(expression):
    current_number = 0
    stack_of_numbers = []
    last_operation = '+'

    for i, character in enumerate(expression):
        if character.isdigit():
            current_number = (current_number * 10) + int(character)
        if character in '+-*/' or i == len(expression) - 1:
            # Evaluate high-precedence operations immediately.
            if last_operation == '+':
                stack_of_numbers.append(current_number)
            elif last_operation == '-':
                stack_of_numbers.append(-current_number)
            elif last_operation == '*':
                stack_of_numbers.append(stack_of_numbers.pop() * current_number)
            else:
                stack_of_numbers.append(int(stack_of_numbers.pop() / current_number))
            last_operation = character
            current_number = 0

    # Sum remaining values in stack now, only additions and subtractions remain.
    result = 0

    for number in stack_of_numbers:
        result += number

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 immediately as there is no expression to evaluate.
Input string with only whitespace	Return 0 since no valid expression is present.
Input string with leading/trailing whitespace	Trim the input string to remove any leading/trailing whitespace before processing.
Consecutive operators (e.g., 3 + - 2)	Handle the sign of the second operator by correctly parsing and applying to the subsequent number.
Division by zero	Return 0, or throw an exception, depending on the specific requirements.
Integer overflow during calculation	Use a larger integer type (e.g., long) or check for overflow before performing the calculation.
Input string with invalid characters (e.g., letters)	Return 0, throw an exception, or filter out invalid characters before processing.
Large numbers and number of operations	The stack based approach will scale to larger inputs and the integer type (int/long) choice affects range.