Microsoft Interview Question for SDE-2s


Team: STB and MVO
Country: India
Interview Type: In-Person




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

private static boolean isBalanced(char[] source) {
		int counter=0;
		for(char c:source)
		{
			if(c=='{')
				counter++;
			else if(c=='}')
			{
				counter--;
			
				if(counter==-1)
					return false;
			}
		}
		return counter==0;
	}

- Vir Pratap Uttam May 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

I too thought of using the stack but realized it is not doing anything better than just keeping a count variable and without the stack it is more space efficient.

bool IsBalanced(char[] code)
{
  int count = 0;
  foreach(char c in code)
  {
    if (c == '{')
      count++;
    else if (c == '}')
    {
      if (count < 0)
        return false;
    }
  }

  return (count == 0);
}

- vstudio April 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Missed the decrement step in the last post!!
bool IsBalanced(char[] code)
{
int count = 0;
foreach(char c in code)
{
if (c == '{')
count++;
else if (c == '}')
{
count--;
if (count < 0)
return false;
}
}

return (count == 0);
}

- vstudio April 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take a stack and scan the input character by character from beginning to end. For every opening brace you encounter, push char '{' on to the stack and for every closing brace pop one '{'. At the end of input stream, if stack is non-empty then it is unbalanced, if not balanced.

Time complexity : O(n)
Space complexity :O(n)

- prakash1529 April 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 3 votes

Slight improvisation on space. Instead of keeping stack, just have an integer variable. Every opening brace you do +1 and every closing brace you do -1. At the end, if the value of the variable is 0, then it is balanced otherwise unbalanced.

Few special cases : For example " }} jfsdj {{ " is unbalanced. So we must return false if at any point of time we encounter '}' and the value of variable is <=0.

- prakash1529 April 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I gave a solution without using any sort of data structure :)

- pavi.8081 April 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How did you solve that without any extra space ? please share.

- XYZ April 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

See the comment by prakash1529 above. I solved in the same way.
Only thing is I didnt have to consider any special case because my logic covered special cases.

For example while processing the braces I maintained that the partial sum of braces (that is adding +1 for '{' and -1 for '}' ) be
always greater than equal to zero.
It can never go negative at any point of processing and must exactly equate to zero at the end.

- pavi.8081 April 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Shall we use three integer variables one for ( and the second for [ and the another one for { and increment these variable when those characters are encountered and decrease those variables when ) and ] and } are encountered

- Ram rs April 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

HashMap<String, String> braceMap = new HashMap<String, String>();
		braceMap.put("}", "{");
		braceMap.put(")", "(");
		braceMap.put("]", "[");
		
		Stack<String> braceStack = new Stack<String>();
		String c;
		boolean l_value = true;
		for (int i = 0 ; i < braces.length(); i++)
		{
			c = String.valueOf(braces.charAt(i));
			if (braceMap.containsKey(c))
			{
				if(braceStack.isEmpty() || ! braceMap.get(c).equals(braceStack.pop()))
				{
					l_value = false;
					break;
				}
			}
			else
				braceStack.push(c);
		}
		if(l_value)
			System.out.println("Valid Braces");
		else
			System.out.println("Invalid Braces");

- Anonymous April 23, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
cosider following cases 1. {{{}}} 2. {}}{ 3. {{{{}}{}} - Anonymous June 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
//Sample code in java {{{ public class ExprStack { public ExprStack() { super(); } public static void main(String[] args) { ExprStack exprStack = new ExprStack(); // System.out.println(exprStack.validate("{(a+b)}{(c*d)[e-f]}")); System.out.println(exprStack.validate("{{{}{}}}")); } public boolean validate(String expr) { if(expr.charAt(0)=='}' || expr.charAt(0)==']' || expr.charAt(0) == ')') return false; Stack<Character> stack = new Stack<Character>(); int i = 0; while(i < expr.length()) { if(expr.charAt(i)=='{' || expr.charAt(i)=='[' || expr.charAt(i)=='(') { stack.push(expr.charAt(i)); } else if(expr.charAt(i)=='}' && !stack.isEmpty() && stack.peek()=='{') { stack.pop(); } else if(expr.charAt(i)==']' && !stack.isEmpty() && stack.peek()=='[') { stack.pop(); } else if(expr.charAt(i)==')' && !stack.isEmpty() && stack.peek()=='(') { stack.pop(); } i++; } if(stack.isEmpty()) { return true; } else { return false; } } } }}} - Prakash October 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

String code = "#{code{anotherCOde}}dsd}}";
		int count = 0;

		for (int i = 0; i < code.length(); i++) {
			if (code.charAt(i) == '{') {
				count++;
			} else if (code.charAt(i) == '}') {
				count--;
			}
		}

		System.out.println(count == 0 ? "true" : "false");

- Sumit November 18, 2013 | 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