Microsoft Interview Question
SDE-2sTeam: STB and MVO
Country: India
Interview Type: In-Person
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);
}
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)
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.
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.
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");
- Vir Pratap Uttam May 12, 2015