Broadsoft Interview Question for SDE1s


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.

- Subbu June 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 27, 2014 | Flag
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()

- Anonymous June 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!).

- Anonymous June 30, 2014 | Flag
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.

- Prabhat June 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

gr8 !! hats off !!

- sedhuait July 09, 2014 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More