Following our previous posts about Uber interview questions, this week we’re going to talk about one of my favorite questions – permutations of an array of arrays.
If you keep following our blog, I hope you can solve this problem by yourself as a lot of ideas and techniques used here are common. Here we go.
Permutations of an Array of Arrays
Given a list of array, return a list of arrays, each array is a combination of one element in each given array.
Let me give you an example to help you understand the question Suppose the input is [[1, 2, 3], , [5, 6]], the output should be [[1, 4, 5], [1, 4, 6], [2, 4, 5], [2, 4, 6], [3, 4, 5], [3, 4, 6]].
This question permutations of an array of arrays has been asked not only by Uber recently, but also a lot of other companies like Google and Facebook. The reason I like it is that candidates really need a solid computer science foundation in order to solve it. Also, it’s not that easy to have bug-free code solution.
If you have followed out last few posts, I hope you can come up with a solution in minutes. There are several very obvious signals in this question that you should be aware of.
Let’s say we want to start with a naive approach. Most people would just try brute force. However, if you think about it for seconds, you’ll realize that brute force will lead you nowhere.
Why? If we have only three arrays in the input, you can easily iterate all elements with three loops. But the input can have any number of arrays, which makes the above approach impossible.
I hope it won’t take you too much time to think about recursion. I would say two signals in the question make me think about recursion or dynamic programming immediately.
First, recursion/DP is usually a great tool for questions about permutations. Another example is print permutations of parentheses.
Second, when we need an unknown number of loops to iterate over all possibilities, recursion/DP is usually the right approach.
Let me briefly explain this point. In essence, the reason that you can’t brute force the solution is that you’ve no idea how many loops to use. However, if you assume that you’ve solved the sub-problem, all you need is to have one loop on the first element and combine with the solution of sub-problem of all the other elements.
So we have the following algorithm:
- Define function permutations(i) returns all permutations using array[i] to array[n] (n is the total number arrays).
- To calculate permutations(i), we can iterate over array[i]. For each number, we add it to the results of permutations(i+1).
- Thus, we can use permutations(i + 1) to calculate permutations(i). When i == n, we should stop the recursion.
Let’s take a look at the code:
Can you point out the biggest issue of this algorithm?
When the number of arrays gets big, res_next stores all permutations in memory, which might be a problem. There might not be a good way to solve this, but suppose we only want to print out all permutations instead of returning them, how can we make it more efficient?
The problem will be very similar to find a path in a maze. You can keep an array of current result. Whenever you are processing an array, just add one number to the result and move on the next array.
After you get a full sized result array, you will start popping up element as a backtracking approach. By doing this, you only need to keep a single array in memory. I’ll leave this as a coding assignment for you.
After reading this post, I hope you’ll have at least two take-aways from permutations of an array of arrays:
- There are lots of “hints” in the questions that help you think about recursion/dynamic programming. So next time when you see them, you should become very “sensitive”.
- Analyzing time/space complexity of recursion/dynamic programming can be challenging, it’s better to start thinking about it for every single question you’ve practiced.
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..