Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

Seems like a dynamic programming problem.

Suppose 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.

Comment hidden because of low score. Click to expand.
0

k in second sentence is actually n. (different from k in last sentence)

Comment hidden because of low score. Click to expand.
1
of 1 vote

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()``````

Comment hidden because of low score. Click to expand.
0

You are using lists and dictionary, won't be O(n^3) in the worst case. But we can replace them with arrays and then it will be O(n^3), so +1 (virtual).

Thanks for the working code (it even has testcases!).

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

Nope. 3 - 1*0, will give 0 by your logic, but you can make 3, if you do the * first.

Comment hidden because of low score. Click to expand.
0
of 0 vote

gr8 !! hats off !!

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.