Salesforce Interview Question
Developer Program EngineersCountry: India
Interview Type: Written Test
Use a stack:
We loop through the string. If we encounter an open parenthesis, we put it on the stack. If we find a close parenthesis, we remove an open parenthesis of the stack- In this case, if we find that there is no open parenthesis on the stack, we know that we have invalid parentheses.
Likewise, If we find that by the end of the string, we still have open parentheses on the stack, it is invalid.
Some code:
boolean isValid(String s) {
Stack stack = new Stack();
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') { stack.push("("); }
else if (s[i] == ')') {
if ( stack.size() > 0) { stack.pop();}
else { return false; }
}
}
return (stack.size() == 0);
}
Interviewer seems to asked for Number of wrong sets in given string .i.e. He doesn't want to check whether parenthesis is balanced or not .
bool IsValidParenthesis(char* expression)
{
stack<char> parenthesis;
char* start = expression;
bool consecutive_push_flag = false;
bool consecutive_pop_flag = false;
while (*start != '\0')
{
if (*start == '(')
{
if (consecutive_push_flag == true)
{
parenthesis.push('#');
}
parenthesis.push(*start);
consecutive_push_flag = true;
consecutive_pop_flag = false;
}
else if (*start == ')')
{
if (parenthesis.empty())
{
return false;
}
if (consecutive_pop_flag == true && parenthesis.top() == '#')
{
return false;
}
consecutive_push_flag = false;
consecutive_pop_flag = true;
parenthesis.pop();
}
else
{
consecutive_push_flag = false;
consecutive_pop_flag = false;
}
++start;
}
if (!parenthesis.empty())
{
return false;
}
return true;
}
bool IsValidParenthesis(char* expression)
{
stack<char> parenthesis;
char* start = expression;
bool consecutive_push_flag = false;
bool consecutive_pop_flag = false;
while (*start != '\0')
{
if (*start == '(')
{
if (consecutive_push_flag == true)
{
parenthesis.push('#');
}
parenthesis.push(*start);
consecutive_push_flag = true;
consecutive_pop_flag = false;
}
else if (*start == ')')
{
if (parenthesis.empty())
{
return false;
}
if (consecutive_pop_flag == true && parenthesis.top() == '#')
{
return false;
}
consecutive_push_flag = false;
consecutive_pop_flag = true;
parenthesis.pop();
}
else
{
consecutive_push_flag = false;
consecutive_pop_flag = false;
}
++start;
}
if (!parenthesis.empty())
{
return false;
}
return true;
}
I do not understand why people are using stack to store braces and count. Why dont you just do one iteration of string and get the result without taking any additional data structure.
Let me know if my approach is slower than the one with stack. I have just started solving questions.
var exp = "((Hello))))))))))))))))";
var openBrCt = 0;
var closeBrCt = 0;
for (var i=0; i<exp.length; i++)
{
if(exp[i]==='(')
openBrCt++;
else if(exp[i]===')')
closeBrCt++;
}
if(openBrCt-closeBrCt == 0)
alert("No error in expression");
else
alert("Open and Close:" + openBrCt + " " + closeBrCt)
alert("There are: " + (parseInt(openBrCt)-parseInt(closeBrCt)) + " wrong braces in expression")
import java.util.Stack;
public class Main {
public static void main(String[] args) {
String s = "(((((A))((B))))(()))";
System.out.println("isBalanced: " + isBalanced(s));
}
private static boolean isBalanced(String s) {
Stack<Character> sk = new Stack<Character>();
boolean bNeverHad = true;
for (char c: s.toCharArray()) {
if ((c != ')') && (c != '}') && (c != ']')) {
// ( ( A ( B
if (!bNeverHad && sk.isEmpty()) {
return false;
}
sk.push(c);
bNeverHad = false;
System.out.println("push: " + c);
} else {
// )
char popc;
if (!sk.isEmpty()) {
popc = sk.pop();
System.out.println(" POP: " + popc);
while ((!sk.isEmpty()) &&
(popc != '(') && (popc != '{') && (popc != '[')) {
popc = sk.pop();
System.out.println(" POP: " + popc);
break;
}
} else {
return false;
}
}
} // for
if (sk.size() > 0)
return false;
return true;
}
/* (non-Java-doc)
* @see java.lang.Object#Object()
*/
public Main() {
super();
}
}
Use Stack.
Push into the stack until you a get a closing brace.
On getting a closing brace, pop out an element from the stack.
If (you got anything but a brace continue popping until you get a brace)
check the brace is a matching one else return "wrong string"
continue with the string
else(if you got a brace on first pop) it would be an extra brace
return "wrong string"
- hm January 17, 2015