Google Interview Question
SDE-2sCountry: India
Interview Type: Written Test
Logic around handling ')', if input is '(' it is just added to stack and stack count is added at the end to account for it.
private static void makevalidparent(string s)
{
Stack<char> parent = new Stack<char>();
int makevalid = 0;
foreach(char c in s)
{
if ( c == '(' )
parent.Push( c );
else if (c == ')')
{
if(parent.Count == 0)
{
makevalid++;
}
else
{
parent.Pop();
}
}
}
makevalid = makevalid + parent.Count;
Console.WriteLine( makevalid );
}
public class MinimumParenthasis {
public static int minimumParenthases(String str)
{
if (str==null || str.length()==0)
return 0;
if (str.length()==1)
return 1;
if (str.charAt(0)=='(' && str.charAt(str.length()-1)==')')
return minimumParenthases(str.substring(1,str.length()-1));
if (str.charAt(0)==')')
return 1+minimumParenthases(str.substring(1));
return 1+minimumParenthases(str.substring(0,str.length()-1));
}
public static void main(String[] args) {
System.out.println(minimumParenthases(")("));
System.out.println(minimumParenthases("(()"));
System.out.println(minimumParenthases("))"));
System.out.println(minimumParenthases("(())"));
System.out.println(minimumParenthases("))(("));
System.out.println(minimumParenthases(")(("));
}
}
There was a bug in the code. This should work:
public class MinimumParenthasis {
public static int minimumParenthases(String str)
{
int closeNeeded=0;
int needed = 0;
for (int i=0;i<str.length();i++) {
if (str.charAt(i)==')' && closeNeeded==0)
needed++;
else
if (str.charAt(i)==')')
closeNeeded--;
if (str.charAt(i)=='(')
closeNeeded++;
}
needed+=closeNeeded;
return needed;
}
public static void main(String[] args) {
System.out.println(minimumParenthases("(()())"));
System.out.println(minimumParenthases("(()"));
System.out.println(minimumParenthases("))"));
System.out.println(minimumParenthases("(())"));
System.out.println(minimumParenthases("))(("));
System.out.println(minimumParenthases(")(("));
}
}
There was a bug in the above code. This should work
public class MinimumParenthasis {
public static int minimumParenthases(String str)
{
int closeNeeded=0;
int needed = 0;
for (int i=0;i<str.length();i++) {
if (str.charAt(i)==')' && closeNeeded==0)
needed++;
else
if (str.charAt(i)==')')
closeNeeded--;
if (str.charAt(i)=='(')
closeNeeded++;
}
needed+=closeNeeded;
return needed;
}
public static void main(String[] args) {
System.out.println(minimumParenthases("(()())"));
System.out.println(minimumParenthases("(()"));
System.out.println(minimumParenthases("))"));
System.out.println(minimumParenthases("(())"));
System.out.println(minimumParenthases("))(("));
System.out.println(minimumParenthases(")(("));
}
}
public class MinimumParenthasis {
public static int minimumParenthases(String str)
{
if (str==null || str.length()==0)
return 0;
if (str.length()==1)
return 1;
if (str.charAt(0)=='(' && str.charAt(str.length()-1)==')')
return minimumParenthases(str.substring(1,str.length()-1));
if (str.charAt(0)==')')
return 1+minimumParenthases(str.substring(1));
return 1+minimumParenthases(str.substring(0,str.length()-1));
}
public static void main(String[] args) {
System.out.println(minimumParenthases(")("));
System.out.println(minimumParenthases("(()"));
System.out.println(minimumParenthases("))"));
System.out.println(minimumParenthases("(())"));
System.out.println(minimumParenthases("))(("));
System.out.println(minimumParenthases(")(("));
}
}
public class MinimumParenthasis {
public static int minimumParenthases(String str)
{
if (str==null || str.length()==0)
return 0;
if (str.length()==1)
return 1;
if (str.charAt(0)=='(' && str.charAt(str.length()-1)==')')
return minimumParenthases(str.substring(1,str.length()-1));
if (str.charAt(0)==')')
return 1+minimumParenthases(str.substring(1));
return 1+minimumParenthases(str.substring(0,str.length()-1));
}
public static void main(String[] args) {
System.out.println(minimumParenthases(")("));
System.out.println(minimumParenthases("(()"));
System.out.println(minimumParenthases("))"));
System.out.println(minimumParenthases("(())"));
System.out.println(minimumParenthases("))(("));
System.out.println(minimumParenthases(")(("));
}
}
def minBrackets(string):
balance = 0 # open paran - close paran (let this >= 0)
unbalancedLefts = 0 # number of close parans when balance is 0
for ch in string:
if ch == '(':
balance += 1
else:
if balance > 0:
balance -= 1
else:
unbalancedLefts += 1
return balance + unbalancedLefts
print(minBrackets( ' () ' )) -> 0
print(minBrackets( ' (() ' )) -> 1
print(minBrackets( ' )(()( ' )) -> 3
public static int getMinInsertion(String string) {
char[] inputString = string.toCharArray();
int counter = 0;
int stackSize = 0;
for (int i = 0; i < inputString.length; i++) {
char c = inputString[i];
if (c == ')')
if (stackSize < 1)
counter++;
else
stackSize--;
else
stackSize++;
}
return stackSize + counter;
}
def minpar(s):
"""Given a string s of parentheses (ex: '(()'), return the minimum number of
parentheses that need to be inserted to make it into a well formed
(balanced) string. Time complexity O(n).
>>> minpar('')
0
>>> minpar(')')
1
>>> minpar('(((s)')
2
>>> minpar(')a(b(c)(')
3
>>> minpar(')a)b)c)')
4
"""
if not s:
return 0
ps = [] # stack of parentheses
for c in s:
if c in '()':
if ps and ps[-1] == '(' and c == ')':
ps.pop()
else:
ps.append(c)
return len(ps)
if __name__ == '__main__':
import doctest
doctest.testmod()
Here is C++ solution running in O(N)
#include <string>
#include <iostream>
using namespace std;
int MinInsertsForBalance (const string&s)
{
int left = 0;
int right = 0;
int missing_left = 0;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == '(')
{
left++;
} else if ( s[i] == ')')
{
if (left > 0) left--;
else {
//can't be matched at all
missing_left++;
}
}
}
return (left+missing_left);
}
int main ()
{
string input = "(((((())))))))";
cout << "(((((()))))))) => min = " << MinInsertsForBalance(input) <<endl;
string input2 = "))(((";
cout << "))((( => min = " << MinInsertsForBalance(input2) <<endl;
return 1;
}
#include <iostream>
#include <string.h>
int main()
{
char string[] = "))(())))((";
int closeNeeded = 0;
int balance =0;
if(string != "")
{
int i=0;
int len = strlen(string);
while(len)
{
char ch = string[i];
std::cout << ch;
switch(ch)
{
case '(':
closeNeeded++;
break;
case ')':
if(closeNeeded > 0)
closeNeeded--;
else
balance++;
break;
default:
break;
}
len--;i++;
}
std::cout << std::endl ;
}
std::cout << balance + closeNeeded << std::endl;
return 0;
}
@cdhsiung, thanks for pointing bug in my code. now, I have modified code to fix that issue
#include <iostream>
#include <string>
using namespace std;
//Returns INT_MIN if input string s contains non paranthes characters
int MinNumInsersertionsForBalancing(const string& s)
{
int i=0;
int leftParanthesisCount = 0;
int rightParanthesisCount = 0;
int leftParanthesisToBeInsert = 0;
while(i < s.length())
{
if(s[i] == '(')
{
leftParanthesisCount++;
}
else if(s[i] == ')')
{
// handle ")(" case
if (leftParanthesisCount <= rightParanthesisCount)
{
leftParanthesisToBeInsert++;
}
else
{
rightParanthesisCount++;
}
}
else
{
// error handling
return INT_MIN;
}
i++;
}
// (leftParanthesisCount - rightParanthesisCount) give us no. of right paranthesis to be insert
return leftParanthesisToBeInsert + (leftParanthesisCount - rightParanthesisCount);
}
int main()
{
cout<<MinNumInsersertionsForBalancing("")<<endl;
cout<<MinNumInsersertionsForBalancing("(()")<<endl;
cout<<MinNumInsersertionsForBalancing("))")<<endl;
cout<<MinNumInsersertionsForBalancing("(())")<<endl;
// important test case, missed this test case initially
cout << MinNumInsersertionsForBalancing("))((") << endl;
cout << MinNumInsersertionsForBalancing(")((") << endl;
return 0;
}
}
- cdhsiung October 18, 2015Time O(n); space O(1).
Play with it: cpp.sh/2aso5