This was 1 of 4 questions given on HackerRank as the first stage for their Entry-Level Engineering Programme 2022 (UK). Python was recommended to be used as that's what they use primarily. 180 minutes long but it was recommended that you try to complete it within 120 minutes.
The question was to write a funcition which would take in a prefix expression as a string, and a hash map of variables and their corresponding ranges (given as a tuple with inclusive lower-bound and exclusive upper-bound) and return the maximum value from evaluating the expression.
e.g expression = " + 1 x", variables = {"x": (1,3)} -> f(x) = 1 + x for 1 <= x < 3 in this case we return 3
Any operator ("+", "-", "", "/" <- integer division) and operand must be seperated by at least one space and operands are positive stictly positive integers in base 10 only (e.g. 1, 22, 85 are valid, -1, 0x43, 0, 012 are not valid).An operator must have exactly two operands otherwise it is invalid. Any invalid expressions should return None.
Examples
-
expression: + 1 5
variables: {}result_expression: 6
-
expression: + 1 2 3
variables: {}result_expression: None
-
expression: + 1
variables: {}result_expression: None
-
expression: 9
variables: {}result_expression: 9
-
expression: * + 1 2 3
variables: {}result_expression: 9
-
expression: + 6 * - 4 + 2 3 8
variables: {}result_expression: -2
-
expression: +- 1 5 3
variables: {}result_expression: None
-
expression: + 1 2
variables: {}result_expression: 3
-
expression: * + 2 x y
variables: {"x": (1,3), "y": (2,4)}result_expression: 12
For real test cases on the platform you could pass 29/31 by implementing the evualation properly and taking into account wither 1 or 2 variables given. The other two test cases used much longer expressions with 5-7 variables which I wasn't able to implement during the test. I think this would be a Leetcode Hard due to having to parse the expression and the inclusion of variables with ranges. It is an extension on Evaluate Reverse Polish Notation.
My Solution
My approach was to create two helper functions:
- The first will convert the string expression to an array, noting if it is valid or not.
- The second will create a 2D array of all the combinations of values for the variables when they are given. E.g. If variables is {"x": (1,3), "y": (2,4)} this helper function will return ["x", "y"], [[1,2], [1,3], [2, 2], [2, 3]].
The main function will then take in the expression and variables, use the first helper function to parse the expression to something simpler to use and if their are no valuables it will evaluate the expression, if there are variables it will sub in each combination returned by the second helper function to the expression and evaluate it finding the maximum value and returning it.
Code:
def clean_expression(expression, variables = None):
if isinstance(expression,list): return expression
if variables == None: variables = {}
expression_array = []
ind = 0
operations = ["+", "-", "/", "*"]
count_vars = []
while ind < len(expression):
if expression[ind] in operations:
# operation must be seperated by space
if ind+1 < len(expression) and expression[ind+1] != " ":
# expression is invalid
return None
else:
expression_array.append(expression[ind])
ind += 1
elif expression[ind] != " ":
operand = ""
while ind < len(expression) and expression[ind] != " ":
operand += expression[ind]
ind += 1
if operand.isnumeric():
expression_array.append(int(operand))
else:
expression_array.append(operand)
if operand not in variables:
return None
elif operand not in count_vars:
count_vars.append(operand)
else:
ind += 1
return expression_array if len(count_vars) <= len(variables) else None
# Time: O(n), Space: O(m) where n is the length of the original expression and m
# is the length of the resulting array
def var_combinations(variables, combinations = None):
if combinations == None: combinations = []
variables_array = [var for var in variables]
combinations = [[i] for i in range(variables[variables_array[0]][0], variables[variables_array[0]][1])]
for j in range(1,len(variables_array)):
new_combinations = []
for combo in combinations:
for k in range(variables[variables_array[j]][0], variables[variables_array[j]][1]):
new_combinations.append(combo + [k])
combinations = new_combinations
return variables_array, combinations
# Let a_i be the size of the range for the ith variable of n, then Time: O(a_1 * a_2 * ... * a_n),
# Space: O(n * a_1 * a_2 * ... a_n)
def evaluate_prefix(expression, variables = None):
operations = ["+", "-", "/", "*"]
expression = clean_expression(expression, variables)
if not expression:
return None
if variables is None:
stack = []
ind = len(expression) - 1
while ind >= 0:
if expression[ind] not in operations:
if expression[ind] == 0:
return None
stack.append(expression[ind])
else:
if len(stack) < 2: return None
a = stack.pop()
b = stack.pop()
if expression[ind] == "*":
stack.append(a*b)
elif expression[ind] == "+":
stack.append(a+b)
elif expression[ind] == "-":
stack.append(a-b)
else:
stack.append(a//b)
ind -= 1
max_result = stack[0]
else:
max_result = float('-inf')
vars, combinations = var_combinations(variables)
for combo in combinations:
new_expression = expression.copy()
for i, var in enumerate(vars):
new_expression = [combo[i] if item == var else item for item in new_expression]
new_expression_result = evaluate_prefix(new_expression, variables=None)
if new_expression_result is not None and new_expression_result > max_result:
max_result = new_expression_result
return max_result if max_result != float("-inf") else None
# Unsure how I'd write the Time/Space for this one given the helper functions?