Bloomberg L.P.

www.bloomberg.com
Employer Engaged

Interview Question

Financial Software Developer Interview New York, NY

How do you remove extra parenthesis in a given equation Ex

  : ((a+b))*c should be converted to (a+b)*c
Answer

Interview Answer

3 Answers

0

I used stacks, but they want something simpler.

Interview Candidate on Feb 15, 2012
0

Just recursion?

Anonymous on Feb 26, 2012
0

My idea is to scan string left to right, when encounter with "((", find the matching "))" by starting. Then decide if the candidate pair can be removed.

My code (java) may be a bit long and can be possibly shortened. But I think the test cases I used may represent the cases they want me to deal with.

class RemoveAdditionalParenthesis
{
    public static void main(String[] args)
    {

        String input = "((1+2+3))+4";//can be shortened to (1+2+3)+4
        String input1 = "((1+2)+(3+5))+4";//Cannot be shortened
        String input2 = "((1+2)+(3)+(4+5))+4";//can be shortened to ((1+2)+(3)+(4+5))+4
        String input3 = "((((1+2)+((3))+((4+5)))))+((4))";//can be shortened to ((1+2)+(3)+(4+5))+(4)
        System.out.println(RemovePar(input));
        System.out.println(RemovePar(input1));
        System.out.println(RemovePar(input2));
        System.out.println(RemovePar(input3));
    }

    public static String RemovePar(String inputExp)
    {
        int startIndex = 0;//global index to keep track of the current focus start position
        while(true)
        {
            char[] inputs = inputExp.toCharArray();
            int candiateStart = -1;
            int candiateEnd = -1;
            for(int i=startIndex; i<inputs.length-1; i++)
            {
                if(inputs[i]=='(')//encounter a opening parenthesis
                {
                    //peek next one
                    if(i+1<inputs.length&&inputs[i+1]=='(')
                    {
                        //candidate pair start
                        candiateStart = i;
                        int currentParDiff = 2;
                        for(int j=candiateStart+2; j<inputs.length; j++)
                        {
                            if(inputs[j]=='(') currentParDiff++;
                            else if(inputs[j]==')') currentParDiff--;
                            if(currentParDiff==0)//find the matched close parenthesis
                            {
                                candiateEnd = j;
                                break;
                            }
                        }
                        break;
                    }
                }
            }
            //now need determine if candiateStart and candiateEnd are removable pairs
            if(candiateStart==-1 || candiateEnd==-1)
                return inputExp;
            else//there is a candiate pair
            {
                System.out.println("candiate pair: ("+candiateStart + ", "+candiateEnd+") for string\""+inputExp+"\"");//debug use
                //check if candiateStart+1 and candiateEnd-1 is a pair?
                int currentParDiff = 1;
                for(int j=candiateStart+2; j<inputs.length-1; j++)
                {
                    if(inputs[j]=='(') currentParDiff++;
                    else if(inputs[j]==')') currentParDiff--;
                    if(currentParDiff==0)//find the matched close parenthesis
                    {
                        //check if j==candiateEnd-1
                        if(j==candiateEnd-1)//this is removable!
                        {
                            inputExp = "";
                            for(int i=0; i<inputs.length; i++)
                            {
                                if(i!=candiateStart && i!=candiateEnd)
                                    inputExp+=inputs[i];
                            }
                        }
                        else
                            startIndex++;//update focus point
                        break;
                    }
                }
            }

        }
    }
}

Anonymous on Mar 13, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.