Broadsoft Interview Question
SDE1sCountry: India
Interview Type: In-Person
Here is python code based on subbu's idea of dynamic programming which gives O(n^3) time algorithm.
It is a quick implementation, and some optimizations can be made.
def compute(lhs, rhs, op):
if op == "+":
return lhs + rhs
if op == "*":
return lhs * rhs
if op == "-":
return lhs - rhs
def get_optimal(M1, m1, M2, m2, op):
l = [compute(M1, M2, op), compute(M1, m2, op), compute(m1, M2, op), compute(m1, m2, op)]
return max(l), min(l)
def get_max(nums, ops):
Max, Min = {}, {}
i = 0
for num in nums:
Max[(i,i)] = num
Min[(i,i)] = num
i += 1
for i in range(0, len(nums)-1):
Max[(i,i+1)] = compute(nums[i], nums[i+1], ops[i])
Min[(i,i+1)] = compute(nums[i], nums[i+1], ops[i])
for d in range(2, len(nums)):
for i in range(0, len(nums) - d):
# Opt[i, i+d] = Opt(Combine(Opt[i, i+k], Opt[i+k+1, i+d]))
Ms, ms = [], []
for k in range(0, d):
M,m = get_optimal(Max[(i,i+k)], Min[(i, i+k)], Max[(i+k+1, i+d)], Min[(i+k+1, i+d)], ops[i+k])
Ms.append(M)
ms.append(m)
Max[(i, i+d)], Min[(i, i+d)] = max(Ms), min(ms)
return Max[(0, len(nums)-1)]
def test(expr_str, nums, ops, expected):
m = get_max(nums, ops)
if m == expected:
print "Pass: ",
else:
print "Fail: ",
print expr_str, "=", m
def main():
expr_str = "3 - 1 * 5 - 2"
test(expr_str, [3,1,5,2], ["-", "*", "-"], 8)
expr_str = " 1 * 2 * 3 * 0 + 3"
test(expr_str, [1, 2, 3, 0, 3], ["*", "*", "*", "+"], 18)
if __name__ == "__main__":
main()
I think we need to do + and - first . Finally do * then only we can get the maximum answer. Just by using divide and conquer break the exp with * operator and evaluate the sub expression and finally evaluate the main exp.
Seems like a dynamic programming problem.
- Subbu June 27, 2014Suppose expression is given as num1 op1 num2 op2 ... num_k
You compute BOTH the Maximum and Minimum possible evaluation of num_i ... num_j.
Then based on op_k, you can decide how to combine (num1 .. numk) opk (numk ... num_j) to get the max and min values for num1 ... numj.