The fourteenth post of the series of programming job interview challenge is out, 79 comments with answers were provided to job interview challenge #13. We didn’t publish a question last week due to a sever lack of time, so another week is gone and here we are again.

Mark R was the first to provide a correct and detailed answer (which I can quote here):

As you examine each character, classify it as either an opening or closing bracket. If it’s an opening bracket, push it onto a stack. If it’s a closing bracket, pop the top character off of the stack; if the stack was empty, or the character was not the matching open bracket, then return an error. At the end of input, if the stack is empty, you have a legal expression.

C++ has a built-in stack class, so this becomes a trivial problem. I’m not sure about other languages. You could always simulate a stack by appending and deleting characters from the end of a string.

So, in one word, the most efficient answer is use a stack. Here is a nice image which was crafted by David Tchepak in his blog post Brackets, braces, parentheses, and other such creatures:


Continue Reading...