Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Problem Challenge 1: Evaluate Expression

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

.....

.....

.....

Like the course? Get enrolled and start learning!
N

neojw1505

· 7 hours ago

This problem seems like it is a divide conquer recursion problem, i dont think it should be under backtracking topic

Pranshu Upadhaya

Pranshu Upadhaya

· a month ago

same as memoized version but pythonic cache is added

from functools import cache

class Solution:

charset = ['+', '-', '*']

@cache

def diffWaysToEvaluateExpression(self, input):

result = []



if all(c not in input for c in self.charset) :

  result.append(int(input))

  return result



for i in range(0, len(input)) :

  if input[i] not in self.charset :

    continue



  left = self.diffWaysToEvaluateExpression(input[0:i])

  right = self.diffWaysToEvaluateExpression(input[i+1:])

  for lp in left :

    for rp in right :

      ch = input[i]

      if ch == '+' :

        result.append(lp + rp)

      elif ch  == '-' :

        result.append(lp - rp)

      elif ch == '*' :

        result.append(
Ben

Ben

· 2 years ago

I struggled to find solutions to Problem Challenges 1, 2, and 3. The preceding challenges used BFS, while these challenges use what I would understand as the Backtracking pattern. Both patterns solve "Subsets" challenges, but only BFS was briefly introduced in the introduction section. Is my understanding correct? Would it make sense to move the problem challenges to the Backtracking section? :)

Dakshesh Jain

Dakshesh Jain

· 2 years ago

This is the same solution but with Return Early, many programmers myself included find this more readable.

class Solution:
  def diffWaysToEvaluateExpression(self, input):
    result = []
    
    # return early instead of using else condition
    if "+" not in input and "*" not in input and "-" not in input:
      result.append(int(input))
      return result

    # continue program if condition is not met
    for i in range(len(input)):
      char = input[i]
      if char.isdigit():
        # this also avoids nesting
        continue

      left_part = self.diffWaysToEvaluateExpression(input[0:i])
      right_part = self.diffWaysToEvaluateExpression(input[i+1:])

      for part_1 in left_part:
        for part_2 in right_part:
          if char == "+":
            res
Show 1 reply
Z

zachery.pang

· 2 years ago

Is space complexity of O(2^N) based on the number of results returned in the output?

Let me know if my interpretation is right:

The number of operators is linear in relation to the length of the expression

1 + 2 * 3 --> has 2 operators. Outputs: [7,9]

2 * 3 - 4 - 5 --> has 3 operators. Outputs: [8,-12,7,-7,-3]

2 * 3 - 4 - 5 + 6 --> has 4 operators. (My own example) Outputs: [20,-4,-24,20,0,13,1,-13,-9,14,-6,13,-1,3]

So given N operators (where length of expression is N + 1), the number of outputs is 2^N, and this is the space required to hold the values. Therefore, space complexity is O(2^N)

M

Michael Shum

· 4 years ago

For the Memoized version, is the runtime the same?

J

J

· 4 years ago

How do both solutions use BFS if they both make recursive calls? In almost all cases, doesn't recursion with some kind of linear data structure input in general imply DFS and not BFS?

Show 1 reply
M

Michael Baggie

· 4 years ago

What number is this on leetcode?

Show 1 reply
D

Daniel Lee

· 4 years ago

For example 2, wouldn't the solution not work if the input was 2*3+4-5 because the output contains duplicate values?

Reading Progress

0%