screen-shot-2016-12-09-at-7-56-46-pm

Uber Interview Questions – Permutations of an Array of Arrays

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

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:

  1. 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”.
  2. 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

Share on Facebook0Tweet about this on TwitterShare on LinkedIn0Share on Reddit0

16 thoughts on “Uber Interview Questions – Permutations of an Array of Arrays

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

  2. 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;
    }

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

Leave a Reply

Your email address will not be published. Required fields are marked *