> A recursive solution springs to mind, but I can recall implementing recursive solutions in production code only a few tens of times over a ten year career.
If you are not comfortable with recursion, just remember: Recursion is really just a free stack. To use your example:
Whenever you see an opening brace, push onto the stack. (Or, make a recursive call, which goes onto the call stack...)
Whenever you see a closing brace, pop off the stack. (Or, return from the recursive call, which then pops off the call stack...)
If the stack isn't empty at end of input, then there are mismatched opening braces. If you ever try to pop from an empty stack, then there are mismatched closing braces.
Thank you for the helpful comment. I can't help but feel you miss the point of my post though. I can solve the problem. Verbally, (but admittedly less eloquently and less complete) I approximately gave your answer in the interview. Give me a quiet Monday morning, a pair of headphones and a compiler/interpreter and I can solve it well.
It's the fact that it is being used as a filter when the person filtering doesn't know what is being filtered in and out.
All in all, it's a spectacular waste of time and money.
I understood your post. I didn't comment on your other points because I didn't feel I had anything to add. I was just trying to be helpful in regards to the particular problem you posted, and for anyone having trouble with recursive problems in general.
If you are not comfortable with recursion, just remember: Recursion is really just a free stack. To use your example:
Whenever you see an opening brace, push onto the stack. (Or, make a recursive call, which goes onto the call stack...)
Whenever you see a closing brace, pop off the stack. (Or, return from the recursive call, which then pops off the call stack...)
If the stack isn't empty at end of input, then there are mismatched opening braces. If you ever try to pop from an empty stack, then there are mismatched closing braces.