Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Use stack.. If you get open bracket push else pop. At the end of expression the stack should be empty.
Using stack you would need extra memory.
using a counter (initial value 0). we can do it just by parsing the string from left, increment counter if it is a open bracket '[' and decrement if it is a closed bracket ']'. At any point if counter is negative return false.
after traversing the string if counter is positive return false. otherwise return true.
int isValidParenthesis(char *str, int len) {
int count = 0, i;
for(i = 0; i < len; i++) {
if (str[i] == '[') {
count++;
}
else if (str[i] == ']') {
count--;
}
if (count < 0) {
return FALSE;
}
}
if (count > 0) {
return FALSE;
}
return TRUE;
}
public static boolean validateparanthesis(String expression){
StringBuilder sb = new StringBuilder();
char[] characters = expression.toCharArray();
for(int i = 0; i< characters.length; i++){
if(characters[i] == '('){
stack.push(characters[i]+"");
}else if(characters[i] == ')'){
sb.append(characters[i]);
if(stack.empty()){
return false;
} else
sb.append(stack.pop());
}
}
String result = sb.toString();
if ((result.length()%2) == 0) {
return true;
}else
return false;
}
Traverse the string of parenthesis gives. At any point no of open brackets >= no of closed brackets
- learner October 21, 2011