CareerCup

Sorry, the interviewer specified that the string contains parenthesis, not that it's composed only of parenthesis, so for instance the test case string "asdba()da(d))" would have to be solved by the algorithm as well.

@rutayanp yea, there were several different questions through the 5 hours that the interview lasted, I believe you should be able to see them all if you check my profile.

Since this is just a string with parenthesis "( and )", just a normal counter should do:

import java.io.*;
import java.util.*;
import java.lang.Math;
public class New
{
public static void main(String[] args)
{
String s="(())))";
int i,count=0,res;
for(i=0;i<s.length();i++)
if(s.charAt(i)=='(')
count++;
else
count--;
res=Math.abs(count);
System.out.println(res);
}
}

Were there multiple coding rounds ? :)

there can be multiple patterns generated as an output. Should we list them all or just returning one string with valid patterns is enough? :)

@rutayanp, the interviewer didn't specify, but he was interested in the outputs in which the least amount of parenthesis have been removed to achieve the balance

Stack<String> st = new Stack<String>();
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(')
st.push(str.charAt(i) + "");
else if (str.charAt(i) == ')'){

if (!st.isEmpty() && st.peek().equals("("))
st.pop();
else
st.push(str.charAt(i)+"");

}
}

System.out.println(st.size());

int count=0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(')
count++;
else if(str.charAt(i) == ')')
count--;
}
System.out.println(Math.abs(count));
return count;

In case the question is not clear: you're supposed to return a new String with the parenthesis removed, not a count.

import sys

inputStr = sys.argv[1]

stack = []
numBracesToRemove = 0;

for c in inputStr:
    if c == '(':
        stack.append(c)
    elif c == ')':
        if len(stack) == 0:
            numBracesToRemove = numBracesToRemove + 1
        else:
            stack.pop()

numBracesToRemove = numBracesToRemove + len(stack)

print 'Number of Braces to Remove for balanced braces count', inputStr, 'is = ', numBracesToRemove

String s = "asdba()da(d))";
		Stack<Integer> stack = new Stack<>();
		StringBuilder builder = new StringBuilder();
		
		for(int i = 0; i < s.length(); i++){
			
			char c = s.charAt(i);
			
			switch (c) {
			case '(':
				
				stack.push(i);
				break;

			case ')':
				
				if (!stack.isEmpty()) {
					
					builder.insert(stack.pop(), "(");
					builder.append(')');
				}
				break;
				
			default:
				builder.append(c);
				break;
			}
		}
		
		System.out.println(builder.toString());

<?php

$string = "asdba((()da(d))";

$newString="";
$openCount=array();
for($i=0;$i<strlen($string);$i++){
    $char = $string[$i];
    if($char == "("){
        $openCount[]=$i;
    }elseif($char == ")"){
        if(sizeof($openCount)>0){
            $lastItem = end($openCount);
            array_pop($openCount);
            $left = substr($newString,0,$lastItem);
            $right = substr($newString,$lastItem);
            $newString=$left."(".$right.")";
        }
    }else
    $newString.=$char;
}

echo $newString; //asdba(()dad())
?>

def reverse(expression):
n = len(expression)
reversed_expression = ''
for i in xrange(n):
reversed_expression = reversed_expression + expression[n - 1 - i]
return reversed_expression


def get_parsed_expression(increment_paren, decrement_paren, expression):
n = len(expression)
intermediate_expression = ''
total_count = 0
for i in xrange(n):
if expression[i] == increment_paren or expression[i] == decrement_paren:
if not (expression[i] == decrement_paren and total_count <= 0):
if expression[i] == increment_paren:
total_count += 1
else:
total_count -= 1
intermediate_expression = intermediate_expression + expression[i]
else:
intermediate_expression = intermediate_expression + expression[i]
return intermediate_expression


def parens(expression):
intermediate_expression = get_parsed_expression(
'(', ')', expression
)

return reverse(get_parsed_expression(
')', '(', reverse(intermediate_expression)
))


print parens('asdba()da(d))') # ()

def reverse(expression):
    n = len(expression)
    reversed_expression = ''
    for i in xrange(n):
        reversed_expression = reversed_expression + expression[n - 1 - i]
    return reversed_expression


def get_parsed_expression(increment_paren, decrement_paren, expression):
    n = len(expression)
    intermediate_expression = ''
    total_count = 0
    for i in xrange(n):
        if expression[i] == increment_paren or expression[i] == decrement_paren:
            if not (expression[i] == decrement_paren and total_count <= 0):
                if expression[i] == increment_paren:
                    total_count += 1
                else:
                    total_count -= 1
                intermediate_expression = intermediate_expression + expression[i]
        else:
            intermediate_expression = intermediate_expression + expression[i]
    return intermediate_expression


def parens(expression):
    intermediate_expression = get_parsed_expression(
        '(', ')', expression
    )

    return reverse(get_parsed_expression(
        ')', '(', reverse(intermediate_expression)
    ))


print parens('asdba()da(d))') # ()

private static int toRemoveCount(String input){
if(input.isEmpty()){
return 0;
}
int removeCount = 0;
Stack<Character> stack = new Stack<>();
for(int i=0;i<input.length();i++){
char currChar = input.charAt(i);
if(currChar == ')'){
if(stack.isEmpty()){
removeCount++;
}else{
stack.pop();
}
}else if(currChar == '('){
stack.push(currChar);
}
}

removeCount += stack.size();

return removeCount;
}

private static int toRemoveCount(String input){
        if(input.isEmpty()){
            return 0;
        }
        int removeCount = 0;
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<input.length();i++){
            char currChar = input.charAt(i);
            if(currChar == ')'){
                if(stack.isEmpty()){
                    removeCount++;
                }else{
                    stack.pop();
                }
            }else if(currChar == '('){
                stack.push(currChar);
            }
        }

        removeCount += stack.size();

        return removeCount;
    }