Microsoft Interview Question
Software Engineer / DevelopersTeam: Bing
Country: India
Interview Type: In-Person
import java.util.Stack;
public class Solution {
public static void main(String[] args) {
String str1 = "(a+b)*(a+c)";
String str2 = "((a+b)+c)+d";
String str3 = "((d*(a+c))+k)";
String str4 = "((a+c))+((d+k))";
String str5 = "((a+v)*(d*h)+c)";
String str6 = "((((a+v)*(d*h)+c)))";
System.out.println(str1 + ": " + getCountOfOuterBrackets(str1));
System.out.println(str2 + ": " + getCountOfOuterBrackets(str2));
System.out.println(str3 + ": " + getCountOfOuterBrackets(str3));
System.out.println(str4 + ": " + getCountOfOuterBrackets(str4));
System.out.println(str5 + ": " + getCountOfOuterBrackets(str5));
System.out.println(str6 + ": " + getCountOfOuterBrackets(str6));
}
private static int getCountOfOuterBrackets(String str) {
Stack<Character> brackets = new Stack<Character>(); // create one stack for entering '(' coming open brackets
Stack<Character> otherCharacters = new Stack<Character>(); // create one stack for counting an alphabets and operator (Other char tha '(';
/*
* Logic is :
* read a string character by character if it is '(' put it into stack::bracket
* if its an other character that '(' and ')' then put it into the stack::otherCharacters
* When We encountered the ')' check stack::otherCharacters is empty ..
* if its empty it mean redundant barcet has come , Increase th count and pop '(' one element from stack::bracket
* If stack::otherCharacters is not empty When ')' has encountered it means.. Its not an redundant bracket
* Pop one element from stack::bracket and and clear the stack::otherCharacters stack
*
*/
int count = 0;
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch == '(') {
brackets.push(ch);
} else if (ch == ')') {
if (otherCharacters.isEmpty()) {
count++;
brackets.pop();
} else {
while (!otherCharacters.isEmpty()) {
otherCharacters.pop();
}
}
} else {
otherCharacters.push(ch);
}
}
return count;
}
}
import java.util.Stack;
public class Solution {
public static void main(String[] args) {
String str1 = "(a+b)*(a+c)";
String str2 = "((a+b)+c)+d";
String str3 = "((d*(a+c))+k)";
String str4 = "((a+c))+((d+k))";
String str5 = "((a+v)*(d*h)+c)";
String str6 = "((((a+v)*(d*h)+c)))";
System.out.println(str1 + ": " + getCountOfOuterBrackets(str1));
System.out.println(str2 + ": " + getCountOfOuterBrackets(str2));
System.out.println(str3 + ": " + getCountOfOuterBrackets(str3));
System.out.println(str4 + ": " + getCountOfOuterBrackets(str4));
System.out.println(str5 + ": " + getCountOfOuterBrackets(str5));
System.out.println(str6 + ": " + getCountOfOuterBrackets(str6));
}
private static int getCountOfOuterBrackets(String str) {
Stack<Character> brackets = new Stack<Character>(); // create one stack for entering '(' coming open brackets
Stack<Character> otherCharacters = new Stack<Character>(); // create one stack for counting an alphabets and operator (Other char tha '(';
/*
* Logic is :
* read a string character by character if it is '(' put it into stack::bracket
* if its an other character that '(' and ')' then put it into the stack::otherCharacters
* When We encountered the ')' check stack::otherCharacters is empty ..
* if its empty it mean redundant barcet has come , Increase th count and pop '(' one element from stack::bracket
* If stack::otherCharacters is not empty When ')' has encountered it means.. Its not an redundant bracket
* Pop one element from stack::bracket and and clear the stack::otherCharacters stack
*
*/
int count = 0;
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch == '(') {
brackets.push(ch);
} else if (ch == ')') {
if (otherCharacters.isEmpty()) {
count++;
brackets.pop();
} else {
while (!otherCharacters.isEmpty()) {
otherCharacters.pop();
}
}
} else {
otherCharacters.push(ch);
}
}
return count;
}
}
The logic is to find to mutual pairs of left and right bracket who are consecutive. We need a stack and some boolean variables to achieve that.
int findDuplicateParenthesis(string expr)
{
bool isPrevLeftBracket = false;
bool isPrevRightBracket = false;
//bool noGapLeft = false;
bool noGapRight = false;
bool isNeighbourAbove = false;
int length = expr.length();
stack<ParenthesisType> parenthesisStack;
for(int i = 0; i < length; i++)
{
char c = expr[i];
if(isspace(c))
continue;
if(c == '(' && !isPrevLeftBracket)
{
isPrevLeftBracket = true;
isPrevRightBracket = false;
if(!parenthesisStack.empty())
{
ParenthesisType pt1 = parenthesisStack.top();
if(pt1.isNeighbourAbove == true)
{
pt1.isNeighbourAbove = false;
parenthesisStack.pop();
parenthesisStack.push(pt1);
}
}
ParenthesisType pt2;
pt2.c = c;
pt2.isNeighbourAbove = false;
pt2.pos = i+1;
parenthesisStack.push(pt2);
}
else if(c == '(' && isPrevLeftBracket)
{
//noGapLeft = true;
ParenthesisType pt1 = parenthesisStack.top();
pt1.isNeighbourAbove = true;
parenthesisStack.pop();
parenthesisStack.push(pt1);
ParenthesisType pt2;
pt2.c = c;
pt2.isNeighbourAbove = false;
pt2.pos = i+1;
parenthesisStack.push(pt2);
}
else if(c == ')' && !isPrevRightBracket)
{
isPrevRightBracket = true;
isPrevLeftBracket = false;
parenthesisStack.pop();
}
else if(c == ')' && isPrevRightBracket)
{
//noGapRight = true;
ParenthesisType pt = parenthesisStack.top();
//condition for duplicate parenthesis
if(pt.isNeighbourAbove == true)
return pt.pos;
parenthesisStack.pop();
}
else
{
isPrevLeftBracket = false;
isPrevRightBracket = false;
}
}
return -1;
}
bool hasDuplicateParenthesis(string s)
{
Stack<char> charStack = new Stack<char>();
foreach (char ch in s)
{
if(ch == ' ') continue;
if (ch == ')')
{
int index = charStack.ToList().IndexOf('(');
if (index == -1)
return false;
if (index == 0)
return true;
for (int i = 0; i <= index; i++)
charStack.Pop();
}
else
charStack.Push(ch);
}
return false;
}
Correcting some typos
correction to your code will make it work.
#include <iostream>
#include<stack>
using namespace std;
int main()
{
stack<char> stackobj;
char input[]="(( a + b ) * (( c + d )))";
int i=0;
while(input[i] != '\0')
{
if(input[i] == '(' || input[i] == '+' || input[i] == '*')
stackobj.push(input[i]);
if(input[i] == ')')
{
if(stackobj.top() == '+' || stackobj.top() == '*')
{
// pop till u find '('
while (stackobj.pop() != '(')
stackobj.pop();
}
else
{
cout << "duplicates parenthesis in the expression, position is " << i<< endl;
return 0;
}
stackobj.pop();
}
i++;
}
if(!stackobj.empty())
{
cout<<"bad input\n">>;
}
else
{
cout <<"No duplicates parenthesis in the expression";
}
return 1;
}
1) take a stack S
2) Keep pushing chars from input in S, one by one
3) if charFromInput == ')' , bool check = true and while(S.pop() != '(');
4) if check == true && nextCharFromInput == ')' && S.pop() == '('
Double parantheses detected.
an o(n) without stack solution:
(assuming the input is well parenthized)
step 1:read character from left untill a '(' is found or input ends.
step 2:if input ends exit;
step 3:if '(' is found check if the next character is'(' ?
if false go to step 1;
else check for the duplicacy for the 2nd '(' recursively//"eg:..(((....)))"
if the the next char(suppose i) of 2nd's matching ')' is
another ')' report 1st '(' duplicate;
else go to next 1 with next symbol as i+1;
here each character is visited only once.so tc is o(n).
an o(n) without stack solution:
(assuming the input is well parenthized)
step 1:read character from left untill a '(' is found or input ends.
step 2:if input ends exit;
step 3:if '(' is found check if the next character is'(' ?
if false go to step 1;
else check for the duplicacy for the 2nd '(' recursively//"eg:..(((....)))"
if the the next char(suppose i) of 2nd's matching ')' is
another ')' report 1st '(' duplicate;
else go to next 1 with next symbol as i+1;
here each character is visited only once.so tc is o(n).
How about this jave code
public class RedundantBrackets {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "((a+b)*(c+d)*(e+f))";
String t;
int length = s.length();
int count=1;
int pos;
int count1 =0;
for(int i=0;i<length;i++){
if(s.charAt(i)=='('){
count++;
}
if(count == 2){
pos = i;
for(int j=i;j<length-1;j++){
if(s.charAt(j) == ')'){
if(s.charAt(j+1) == ')' && (j+1) != length-1){
System.out.println("Redundant bracket present at pos : "+j);
break;
}
}
}
}
}
}
}
I found a much elegant way to solve this problem
#include<iostream>
#include<stack>
#include<conio.h>
using namespace std;
int main()
{
stack<char> pstack;
stack<int> status;
int flag = 0;
char* expr = "(( a + b ) * (( c + d )))";
int i=0;
int pos;
while(expr[i]!='\0')
{
//cout<<"\n In Loop "<<i<<" : "<<expr[i];
if(expr[i] == ' ')
{
i++;
continue;
}
else if(expr[i]=='(')
{
pstack.push('(');
status.push(i);
status.push(0);
}
else if(expr[i] == ')')
{
flag = status.top();
status.pop();
pos = status.top();
status.pop();
pstack.pop();
if(flag == 0)
{
cout<<"Duplicate Paranthesis End Found at : "<<"("<<pos<<","<<i<<" ) ";
getch();
return 0;
}
}
else
{
status.pop();
status.push(1);
}
i++;
}
getch();
}
We can solve this problem using a single stack. We push open brackets and operators on to a stack. When we encounter a closing bracket, we pop till we reach an open bracket.
The trick is that when we encounter an open bracket and start popping, we MUST encounter at least 1 operator. If we don't, then we know that there is extra parentheses.
Let's go through several cases:
((a+b) * (c+d)) - No extra brackets
Reading from left to right:
1. Push '('
2. Push '('
3. Push '+'
4. Encountered ')', pop '+' and '(' - since we found an operator, this is acceptable.
5. Push '*'
6. Push '('
7. Push '+'
8. Encountered ')', pop '+' and '(' - since we found an operator, this is acceptable.
9. Encountered ')', pop '*' and '(' - since we found an operator, this is acceptable.
Now let's look at a case of extra parentheses:
((a+b) * ((c+d)))
You can dry run this yourself, but we will catch duplication, when we are popping the 2nd to last ')' off the stack, since we will not encounter any operator there !
def detectExtraParanthesis(expression):
stack = list()
check = False
for char in expression:
if (char != ')'):
if (check):
check = False
stack.append(char)
else:
check = True
#if (len(stack) == 0):
#return False
while(char != '(' and len(stack) != 0):
popped = stack.pop()
if (popped == '(' and check == True):
return False
elif (popped == '(' and check == False):
break;
else:
check = False
if (len(stack) == 0):
return True
exp = "((a+b)))"
result = detectExtraParanthesis(exp)
if (result):
print("No Duplicate Paranthesis")
else:
print("Duplicate Paranthesis")
import java.util.Stack;
public class Solution {
public static void main(String[] args) {
String str1 = "(a+b)*(a+c)";
String str2 = "((a+b)+c)+d";
String str3 = "((d*(a+c))+k)";
String str4 = "((a+c))+((d+k))";
String str5 = "((a+v)*(d*h)+c)";
String str6 = "((((a+v)*(d*h)+c)))";
System.out.println(str1 + ": " + getCountOfOuterBrackets(str1));
System.out.println(str2 + ": " + getCountOfOuterBrackets(str2));
System.out.println(str3 + ": " + getCountOfOuterBrackets(str3));
System.out.println(str4 + ": " + getCountOfOuterBrackets(str4));
System.out.println(str5 + ": " + getCountOfOuterBrackets(str5));
System.out.println(str6 + ": " + getCountOfOuterBrackets(str6));
}
private static int getCountOfOuterBrackets(String str) {
Stack<Character> brackets = new Stack<Character>(); // create one stack for entering '(' coming open brackets
Stack<Character> otherCharacters = new Stack<Character>(); // create one stack for counting an alphabets and operator (Other char tha '(';
/*
* Logic is :
* read a string character by character if it is '(' put it into stack::bracket
* if its an other character that '(' and ')' then put it into the stack::otherCharacters
* When We encountered the ')' check stack::otherCharacters is empty ..
* if its empty it mean redundant barcet has come , Increase th count and pop '(' one element from stack::bracket
* If stack::otherCharacters is not empty When ')' has encountered it means.. Its not an redundant bracket
* Pop one element from stack::bracket and and clear the stack::otherCharacters stack
*
*/
int count = 0;
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch == '(') {
brackets.push(ch);
} else if (ch == ')') {
if (otherCharacters.isEmpty()) {
count++;
brackets.pop();
} else {
while (!otherCharacters.isEmpty()) {
otherCharacters.pop();
}
}
} else {
otherCharacters.push(ch);
}
}
return count;
}
}
void FindDuplicateParethesis(char* input)
{
if(input == NULL)
return;
int len =strlen(input);
if(len == 0)
return;
std::stack<int> s;
for(int i = 0; i < len; ++i)
{
if(input[i] != ')')
{
s.push(i);
}
else
{
int index = s.top();
s.pop();
if(input[index] == '(')
{
printf("uncessary Parethesis at position %d and %d\n", index, i);
}
else
{
while(!s.empty())
{
index = s.top();
s.pop();
if(input[index] == '(')
break;
}
}
}
}
if(!s.empty())
{
printf("bad input\n");
}
}
check your code against each of the inputs:
( ( ( a * b ) + ( c * d ) ) )
( ( a + b ) * ( c + d ) )
( ( ( a + b ) ) * ( c + d ) ) )
That's because your inputs contain extras white spaces. If you really need the solution to work with extra white spaces between, simply add check for white spaces. That's all.
We can do it by using stack.
if we found "(" we push it to the stack and if we found ")" we pop the "(" from stack. at the end if we have "(" on stack or ")" on the expression parenthesis does not match it have duplicate.
That's not the answer. In the case listed in the question,actullay, nothing will left on the stack finally because they're exactlly mathed but there are duplicates.
Yes, basic idea is to use the stack, but you need to tweak a little to figure out duplicate brackets.
if between two consecutive left brackets and consecutive right brackets, you don't have any operator or operand, then duplicate.
Hi,
By using stack we can find the position of duplicate parenthesis in the expression, here is the code in c++.
#include <iostream>
#include<stack>
using namespace std;
int main() {
stack<char> stackobj;
char input[]="(( a + b ) * (( c + d )))";
int i=0;
while(input[i] != '\0') {
if(input[i] == '(' || input[i] == '+' || input[i] == '*')
stackobj.push(input[i]);
if(input[i] == ')') {
if(stackobj.top() == '+' || stackobj.top() == '*')
stackobj.pop();
else {
cout << "duplicates parenthesis in the expression, position is " << i<< endl;
return 0;
}
stackobj.pop();
}
i++;
}
cout <<"No duplicates parenthesis in the expression";
return 1;
}
Any comments???
correction to your code will make it work.
#include <iostream>
#include<stack>
using namespace std;
int main()
{
stack<char> stackobj;
char input[]="(( a + b ) * (( c + d )))";
int i=0;
while(input[i] != '\0')
{
if(input[i] == '(' || input[i] == '+' || input[i] == '*')
stackobj.push(input[i]);
if(input[i] == ')')
{
if(stackobj.top() == '+' || stackobj.top() == '*')
{
// pop till u find ')'
while (stackobj.pop() != '(')
stackobj.pop();
}
else
{
cout << "duplicates parenthesis in the expression, position is " << i<< endl;
return 0;
}
stackobj.pop();
}
i++;
}
if(!s.empty())
{
printf("bad input\n");
}
else
{
cout <<"No duplicates parenthesis in the expression";
}
return 1;
}
Correcting some typos
- Ashish December 10, 2011correction to your code will make it work.
#include <iostream>
#include<stack>
using namespace std;
int main()
{
stack<char> stackobj;
char input[]="(( a + b ) * (( c + d )))";
int i=0;
while(input[i] != '\0')
{
if(input[i] == '(' || input[i] == '+' || input[i] == '*')
stackobj.push(input[i]);
if(input[i] == ')')
{
if(stackobj.top() == '+' || stackobj.top() == '*')
{
// pop till u find '('
while (stackobj.pop() != '(')
stackobj.pop();
}
else
{
cout << "duplicates parenthesis in the expression, position is " << i<< endl;
return 0;
}
stackobj.pop();
}
i++;
}
if(!stackobj.empty())
{
cout<<"bad input\n">>;
}
else
{
cout <<"No duplicates parenthesis in the expression";
}
return 1;
}