Interview Question

Web Developer Interview

-

Google

1) Given a string of parantheses, check if the string is valid. ex: [[]] is valid, ][][ is not valid. How would you solve if the parantheses could be of different types like {,[,(

AnswerAdd Tags

Interview Answers

6 Answers

5

Stack the parenthesis up. 1st of course the first parenthesis will go on to the stack. If you see a closing parenthesis, pop the stack and see if the parenthesis matches the one which is just read(closing one), if no match? error else keep going.

Amit on

3

Use a counter to track the status. Stack solution is no difference from this. Seeing an opening parenthesis increment the counter. Seeing a closing parenthesis decrement the counter. Check the counter is always non-negative. Counter has to be zero when string ends.

z on

1

To Aegis: If you take "[" as 1 and "]" as -1, then ][][ starts from -1. We can say that's invalid right away.

lsk on

0

I wrote this program using Javascript. Please check the solution. This would cover both cases, 1. The same type of Parenthesis {} or [] 2. Different type of Parenthesis [{( ... function parenthesisChecker(str) { let stack = []; const openingParenthesis = ['{','(','[']; const closingParenthesis = ['}',')',']']; let result = true; for(let index = 0, length = str.length; index -1){ stack.push(char); } if(closingParenthesis.indexOf(char) > -1){ switch(stack.pop()){ case '{': result = char === '}'; break; case '(': result = char === ')'; break; case '[': result = char === ']'; break; } // if result is false then immidiately return 'Non balanced' if(!result) { return "String is not balanced"; } } } return "String is balanced"; } const str = "[()]{}{[()()]()}"; console.log("parenthesis-checker -> " + parenthesisChecker(str));

Amit Bansal on

1

I would compress the level storage by keeping a Stack> and for opening delimiters that are the same type as stack.Peek() just increment its depth instead of pushing a new level tuple. So for example, - the degenerate form of only having one type of delimiter pair to parse such as "((((())))()()())" would only use one stack entry no matter how long and fancy the string is. - "([[][][[[]]]]{{}})" would only use 3 total pushes, and only 2 at any one time are present on the stack.

redgiant on

1

Z: that does not work. They are balanced. Look at the example: ][][ would pass on your input.

Aegis on

Add Answers or Comments

To comment on this, Sign In or Sign Up.