Some dev members are solving some problems here from the "Daily Programming Problem" website. It follows a basic premise: you get a programming problem on your email every single day. It's usually an algorithmic style problem that's very common in interviews with many companies and its usage is increasing. Their idea is if you attempt to solve a different problem everyday, you'll notice some patterns and will get good at it. It's at least being a good exercise for me, since I'm quite rusty.
(By the way, I think these problems are absolutely useless in their intent and should be abolished entirely. They are not a proxy for anything but logical thinking and narrow algorithmic knowledge, which is not a good indicator of good working skills, but, it is what it is.)
One of the latest problems I got was this:
This problem was asked by Facebook.
Given a string of round, curly, and square open and closing brackets, return whether the brackets are balanced (well-formed).
For example, given the string "([])", you should return true.
Given the string "([)]" or "((()", you should return false.
Analyzing the problem
When faced with a new algorithmic problem that you haven't seen before, it's useful to try and map it to a simpler version, see if you have the knowledge to solve that one, and try to generalize your solution and/or adapt what you have to allow you to reach a solution to the problem at hand.
The simplification we can take advantage of here is as follows:
- What if we had only a single type of parentheses?
With a single type of parentheses, we can use a stack in order to check whether the parentheses are balanced or not: when we have a closing parenthesis, we push to the stack, when we have an opening one, we pop. If we reach the end of the string and our stack is empty, then the string is well-balanced. For all other cases, such as, non-empty stack, or inability to pop (if we have a closing parenthesis before an opening one), then the string is not well balanced.
Can we apply this to our problem?
Patterns in the more general problem
It turns out that the exact operations we did for one single type of parentheses, can also work for more than one type, since, if a string is well-balanced, then each type of distinct parentheses should be, itself, well-balanced. Or... should it?
Let's take this example:
{[}]
Each of the two sets of parenthesis is well-balanced, but the combination of the two is not.
Expanding the problem to use more parentheses, doesn't affect our solution down the happy path, where we can use a stack for each type of parentheses and run the normal algorithm (we can use a single stack also which makes the check for the incorrect combination of parentheses easier but I like to visualize it as an extension of the single solution with more than one stack).
A solution
iterate over the string and for each opening parentheses, check for each of the other types as closing and if found mark it as not well-balanced.
Otherwise, use a stack for each type of parentheses and run our normal algorithm. If all stacks are empty return well-balanced else not well-balanced.
(We can use a single stack and when we pop, we can compare the popped value with the previous one and if they don't match, we return false immediately. The idea is to "tag" each type and then check the tags within a single stack, but adds complexity that is "outside" of our algorithm in the first linear time check)
Conclusions
Hope you liked to read and learned something new :) Suggestions for improvements are always welcome!!
Top comments (0)