Solution: Problem Challenge 1: Evaluate Expression

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Problem Challenge 1: Evaluate Expression

Table of Contents

Contents are not accessible

Problem Statement

Given an expression containing digits and operations (+, -, *), find all possible ways in which the expression can be evaluated by grouping the numbers and operators using parentheses.

Example 1:

Input: "1+2*3"
Output: 7, 9
Explanation: 
  1+(2*3) => 7
  (1+2)*3 => 9

Example 2:

Input: "2*3-4-5"
Output: 8, -12, 7, -7, -3 
Explanation: 
  2*(3-(4-5)) => 8
  2*(3-4-5) => -12
  2*3-(4-5) => 7
  2*(3-4)-5 => -7
  (2*3)-4-5 => -3

Solution

This problem follows the Subsets pattern and can be mapped to Balanced Parentheses. We can follow a similar BFS approach.

Let’s take Example-1 mentioned above to generate different ways to evaluate the expression.

We can iterate through the expression character-by-character.
we can break the expression into two halves whenever we get an operator (+, -, *).
The two parts can be calculated by recursively calling the function.
Once we have the evaluation results from the left and right halves, we can combine them to produce all results.

Code

Here is what our algorithm will look like:

Python3

. . . .

Time Complexity

The time complexity of this algorithm will be exponential and will be similar to Balanced Parentheses. Estimated time complexity will be $O(N*2^N)$ but the actual time complexity $(O(4^n/\sqrt{n})$ is bounded by the Catalan number and is beyond the scope of a coding interview. See more details here.

Space Complexity

The space complexity of this algorithm will also be exponential, estimated at $O(2^N)$ though the actual will be $(O(4^n/\sqrt{n})$ .

Memoized version

The problem has overlapping subproblems, as our recursive calls can be evaluating the same sub-expression multiple times. To resolve this, we can use memoization and store the intermediate results in a HashMap. In each function call, we can check our map to see if we have already evaluated this sub-expression before.

Here is the memoized version of our algorithm:

Python3

. . . .

Complexity Analysis

Time Complexity

The time complexity of the given code is $O(2^n \cdot n)$ , where (n) is the length of the input string. This complexity arises from:

Recursive Calls: The function recursively splits the input string at each operator. For each operator, it recursively evaluates all possible left and right subexpressions. This results in exponential growth in the number of subproblems.
Work per Subproblem: For each recursive call, the function performs $O(n)$ work to split the string and process the results from the subexpressions.

Space Complexity

The space complexity is $O(2^n \cdot n)$ , due to:

Memoization Map: The map stores results for each unique subexpression, potentially resulting in $2^n$ different entries.
Recursive Call Stack: The depth of the recursion tree can be (O(n)) in the worst case, where (n) is the length of the input string.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible