We’ve received a lot of feedback from our previous posts. Some readers pointed out bugs in the code and hopefully we’ve fixed all of them. Also, a lot of people are asking for more posts about dynamic programming/recursion. That’s why this week we’d like to talk about the question – permutations of parentheses.
Many people are afraid of this topic because it can be hard to come up with the solution if you haven’t practiced enough. On the flip side, the good news is that just because this topic is relatively difficult, the question cannot be too hard in a coding interview (otherwise, no one could solve it).
This week, we’ll continue to discuss this topic with a Uber interview question, but the analysis/solution is slightly different.
Permutations of Parentheses
Print all possible n pairs of balanced parentheses.
For example, when n is 2, the function should print “(())” and “()()”. When n is 3, we should get “((()))”, “(()())”, “(())()”, “()(())”, “()()()”.
The question has been asked by Uber recently (as of the time of writing). I would say the question is slightly harder than it seems to be, but if you want to pass interviews from top companies like Uber, Google, etc., you should be able to solve this type of problems.
The question permutations of parentheses has also been asked by many other companies.
As a general rule, we should start with a simple solution. Try to solve the problem with the most naive approach and don’t worry about the performance. However, if you think about this for a while, you might realize that it’s really hard to print all permutations with a brute force approach.
Usually, when you have to use an infinite number of loops, it’s a strong signal that you might look for recursion/dynamic programming. It’s worth to note that in this post, I don’t really distinguish between recursion and dynamic programming, because the essence for both is to break the problem into sub-problems, which is what I really want to emphasize.
In addition, if you have solved a lot of coding questions, you may notice that when asked for permutations, recursion is usually a great tool. Another example is to print all permutations of an array.
Following this idea, we should think about whether we can break the problem into smaller sub-problems. If we can successfully come up the recursion formula, the problem is at least half done.
More often than not, we just use the length n to denote a sub-problem. If we know the solution of n-1, n-2… Can we solve the case of n? Not really, because if it starts with “((“, the solution of n-2 won’t help.
Therefore, a better way to denote a sub-problem is use two variables (left, right), which indicates how many left/right parenthesis left. So we can have the following algorithm:
- We start with left = n and right = n and an array results to store parentheses.
- As long as left > 0, we can always append “(“ to results, then the problem becomes (left – 1, right).
- When left < right, we can also append “)” to results, then the problem becomes (left, right – 1).
- When left = right = 0, we can print results.
Note, left should never be greater than right.
As you can see, we are not using extra memory (except results) to store intermediate results. Therefore, some computations are redundant. For example, When n=8 and results start with “(())” and “()()”, we’ll call print_parentheses(6, 6) twice.
The trade-off here is that you need a lot of extra memory to store all intermediate results, especially the results array should be kept.
Two takeaways from this post is that:
- Be sensitive about when we should consider recursion/dynamic programming
- Denoting the sub-problem is the key to the recursion formula. Sometimes, we need more than one variables.
By the way, if you want to have more guidance from experienced interviewers, you can check Gainlo that allows you to have mock interviews with engineers from Google, Facebook, Uber etc..