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], [4], [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.

## Analysis

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.

## Recursion

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
returns all permutations using**permutations(i)**to*array[i]*(n is the total number arrays).*array[n]* - To calculate
we can iterate over**permutations(i)**,. For each number, we add it to the results of*array[i]*.*permutations(i+1)* - Thus, we can use
to calculate*permutations(i + 1)*. When*permutations(i)*, we should stop the recursion.*i == n*

Let’s take a look at the code:

## Continue

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.

## Summary

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..

The post is written by
**
Gainlo** - a platform that allows you to have mock interviews with employees from Google, Amazon etc..

I'd like to learn more

This is combination, not permutation. They are not the same.

@Lei Ma

This is a permutation problem, not combination.

With combination, order does not matter.

With Permutation, order matters.

If we were to alter the example data to be [[1, 2, 3], [4], [1, 2, 3]]:

Choosing 1, 4, 3 would be different than choosing 3, 4, 1.

For permutations we would print both, for combination we’d only print one as they are the same combination.

The algorithm requires a permutation approach even if the data doesn’t demonstrate it.

I do agree that the given example data makes it seem like combination since there is no repeated numbers.

Why doesn’t the code show up? All I see is a huge “-” minus sign

Hi Victory,

Sorry for the inconvenience. The code is back.

Why is code not visible?

can any one provide a complete solution ?

Hi Mamon,

Sorry for the inconvenience. The code is back.

Jake, Still I do not see the code

So true. Honesty and everything rezdcnigeo.

Nice problem. Can’t see your code because the image doesn’t load. I think my solution is the optimal one but I would love to see your approach

Hi Alex,

Sorry for the inconvenience. The code is back.

Thanks 🙂

not code

An iterative solution

public List<List> perms(List<List> slist) {

List<List> res = new ArrayList();

res.add(new ArrayList());

for (List slistItem: slist) {

List<List> newRes = new ArrayList();

for (Integer i: slistItem) {

for(List resItem: res) {

List newResItem = new ArrayList(resItem);

newResItem.add(i);

newRes.add(newResItem);

}

}

res = newRes;

}

return res;

}

It is cartesian product of an array of arrays

Exactly!

>> There are lots of “hints” in the questions that help you think about recursion/dynamic programming.

Sorry, I couldnt see DP here. Isn’t this just recursive backtracking?

Awesome post…..!!!!!

public static List<List> permutate(int[][] arr){

List<List> result = new ArrayList();

permutateHelper(arr,0,result, new LinkedList());

return result;

}

public static void permutateHelper(int[][] arr, int arrIndex, List<List> result, LinkedList partial){

if(partial.size() == arr.length || arrIndex >= arr.length){

ArrayList tmp = new ArrayList(partial);

result.add(tmp);

return;

}

int[] currArr = arr[arrIndex];

for(int i=0; i <currArr.length; i++ ){

partial.add(currArr[i]);

permutateHelper(arr, arrIndex+1, result,partial);

partial.removeLast();

}

}