Permutation of multiple arrays and iterator – code

Permutation of multiple arrays and iterator has two tasks. First is the permutation of multiple arrays and output as one single array. The second is to implement the iterator of this new array.

Permutation is an important topic in the fields of combinatorics. It is usually implemented using recursion. The wrapper method declares the variables to store output and calls helper method. The helper calls itself to retrieve elements in arrays and re-compose them. The output is kind of a 2D Array (it is Set of Set in our implementation).

To implement iterator, we need override hasNext() and next() methods. Since the element is Set in the Set, we can use Set iterator defined in Java APIs.

Amazon Interview Question (CareerCup):
x={a,b,c}, y={p,q}, z={r,s}
Define a Operation, x * y * z = {{a,p,r},{a,p,s},{a,q,r},{a,q,s}……{c,q s}}
Is to output all the results in the order of each subset, implementing a class iterator that has Next() and hasNext() methods

Facebook interview question (CareerCup):
Interleave list of lists in Java
Example:
input = [[1,2,3], [9, 0], [5], [-4,-5,-2,-3,-1]];
output = [1,9,5,-4,2,0,-5,3,-2,-3,-1]

Java Code:

Output:
[[a, p, r], [a, p, s], [a, q, r], [b, p, r], [a, q, s], [b, p, s], [b, q, r], [c, p, r], [b, q, s], [c, p, s], [c, q, r], [c, q, s]]
Permutation of arrys:
[a, p, r]
[a, p, s]
[a, q, r]
[b, p, r]
[a, q, s]
[b, p, s]
[b, q, r]
[c, p, r]
[b, q, s]
[c, p, s]
[c, q, r]
[c, q, s]

O Notation:
Time complexity: O(n*k)
Space complexity: O(n*k)

Credit:
Thanks to François Lejosne to point out the problem in my YouTube tutorial. If you have any questions or want to put comments, please post there as well. I appreciate it!

Action Items:
Download IteratorForPermKArrays.java
Permutation of multiple arrays and iterator tutorial
The complete list of coding interview questions

Comments are closed