CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Google Interview Question for SDE-2s


Country: India
Interview Type: Written Test
More Questions from This Interview



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

#include <iostream>
#include <string>

using namespace std;

int MinNumInsersertionsForBalancing(const string& s)
{
	int numberLeft = 0;
	int numberToInsert = 0;
	
	for(int i = 0; i < s.size(); i++)
	{
		if (s[i] == '(')
		{
			numberLeft ++;
			numberToInsert ++;
		}
		else if (s[i] == ')')
		{
			if(numberLeft)
			{	
				numberLeft--;
				numberToInsert--;
			}
			else
			{
				numberToInsert++;
			}
		}
		else
		{
			cout<<"Unexpected character:" <<s[i];
			return -1;
		}
	}
	
	return numberToInsert;
}
			
int main()
{
	cout<<"Enter a string consisting of '(' and ')':";
	string in;
	cin>>in;
	
	int ret = MinNumInsersertionsForBalancing(in);
	
	if(ret >= 0)
		cout<<endl<<ret<<" to print to make it well-formed.";
	
	return 0;

}

Time O(n); space O(1).
Play with it: cpp.sh/2aso5

- cdhsiung October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

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 );
        }

- c.prashanth85 October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I came up with the same solution. But you don't need a stack, one integer counter is enough.

- damluar October 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

public static int findMinForBalancing(String par)
    {
        int currCount = 0;
        int noToAdd = 0;

        for(int i = 0; i<par.length(); i++)
        {
            char c = par.charAt(i);

            if(c == ')')
            {
                if(currCount>0)currCount--;
                else noToAdd++;

            } else if(c == '(') currCount++;

        }

        noToAdd += currCount;
        return noToAdd;
    }

- krbchd October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

All answers seem pretty simple but i cant figure out how to probe that is an optimal insertion of parenthesis.

- MAX October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

An important comment: in every prefix #'(' >= #')'
1. have a variable calls x
2. pass from right to left, if you see '(' than x++, else x--
3. whenever x=-1, add '(' before the current char -> x=0
4. after you finish check x and add x ')' to the end of the string

- naor October 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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(")(("));
		
	}

}

- AbstractInstance October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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(")(("));
		
	}

}

- AbstractInstance October 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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(")(("));
		
	}

}

- AbstractInstance October 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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(")(("));

}

}

- AbstractInstance October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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(")(("));
		
	}

}

- AbstractInstance October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous October 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- tizianoP October 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- constt October 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- hankm2004 October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Mine is

int MinNumInsersertionsForBalancing(const string& s) {
	int insertions = 0;
	int balance = 0;

	for (char c : s) {
		if (c == '(') {
			balance++;
		}
		else if (c == ')') {
			if (balance <= 0)
				insertions++;
			else
				balance--;
		}
	}
	return insertions + balance;
}

- jmmmm October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

All this solutions seem pretty simple but i can't figure out how to prove that it is an optimal parenthesis insertion.

- maxramirex October 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Neeba November 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
Can any body tell me why this wouldn't work? {{{ int numBalance(string s) { int balance=0; foreach(char ch in s) if(ch=='(') balance++; else if (ch==')') balance--; return Math.Abs(balance); } }} - Tewelde November 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

check this input ")(("

- siva.sai.2020 November 09, 2015 | Flag
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

I am afraid it is not correct with input ")("

- cdhsiung October 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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;
}

- siva.sai.2020 October 19, 2015 | Flag


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