Discussion on: Algorithm 202 (Interview Question): Matching Parenthesis in 2 Ways

These are both good initial implementations to the balanced parentheses problem. Either of these will give the interviewer the opportunity to ask if there are any refactors you would consider for time optimization, memory optimization, readability, modularity, etc., and they like being able to ask that. In fact, some companies will give interviews so intent on "starting with the most straightforward approach" that they'll give you lower consideration for the role you're interviewing for, so this is a really good function to offer as your initial answer.

If your interviewer does ask for refactoring ideas, I noticed a few from when I've answered this question that can apply to your implementation:

The first refactor has to do with sanitizing the input string: Unless an interviewer asks you to remove all of the non-parentheses characters from the input, it's more efficient to skip this. This is because running the input through a regular expression will add at least one extra cycle of iterating through the string to compare each character to the matchable pattern. Since you're already going to compare each character to entries within a map in order to determine what other character they're balanced by, you can lazily filter out the non-parentheses characters there; the map will ask, "What balances the character 'a'? Nothing? Moving right along, then! :D" This makes you lose the opportunity to from the function early if the string isn't an even number of characters long (very clever optimization, by the way!). The tradeoff is that you can check for balanced parentheses running through the entire string exactly once this way. I'm not 100% sure which technique will run faster, but running through the string once is at least less work, theoretically, so I figured it's worth noting.

Another detail I noticed is that your implementation checks for proper (([{}])) nesting in addition to parentheses being balanced (([{)]}). If this is a requirement of the interview problem when you receive it, then there's no reason to switch away from using the stack to check for balance. If nesting isn't important to check for, though, you can use a collection of counters for the opening parenthesis characters, incrementing their values when you iterate over one of them, and decrementing when you see a closing parenthesis. Doing this, you would switch from checking that the closing brace matches the most recent opening brace, and instead return early if any of the counts ever becomes a negative number.

Once again, great post! 👍