How can I generate all possible sorted arrays from alternative elements from two sorted arrays?

Question

I recently came across this question in an interview. I could not answer this question. I started with, take the first element from the first array, and then find how many elements are larger than this element in another array. But then, I mean, I don’t know, I could not really form a solution. The problem is this:

For two sorted arrays, A and B generate all possible arrays, so the first element is taken from A, then from B, then from A, etc. in ascending order until the arrays are exhausted. Generated arrays must end with an element from B.

Eg: A = {10, 15, 25} B = {1, 5, 20, 30} The resulting arrays are: 10 20 10 20 25 30 10 30 15 20 15 20 25 30 15 30 25 30 

I'm not looking for code, just algo / pseduo code will be fine. Thanks!

Answer 1

The BFS solution offered by @dpmcmlxxvi is interesting. In addition, I would suggest a recursive option. Some highlights:

• one of the input arguments to your recursive function should be a boolean that will indicate whether to add an element from A or from B; you will alternate this value in subsequent recursive calls

• arrays are sorted - use this information! When you see sorted arrays, always think about binary search - in this case you must recursively pass the last added element, and then in another array a binary search for the first element that is larger than this last element

• if the last item added was from B, add the current working array to the resulting list

Answer 2

How to use a directed graph with finding BFS paths.

• Create a directed graph where a directed edge is created from an element in array A to each element in array B if this element in B is larger. And vice versa. A directed edge is created from an element in array B to each element of array A, if this element is larger.
• Select an item from A
• Then use BFS to create all possible paths.
• Each time a path includes an element from B, add this subdirectory to the list of solutions to your paths
• Stop when all A elements have been used as a search key.

Update

At the suggestion of @MiljenMikic, you can use the fact that arrays are sorted, speeding up step 1. You do not need to search for all elements in another array to find elements of a larger size. Just follow the last found and move the pointer forward when searching.

Answer 3

A Java-based recursive simple solution could be:

 public static void main(String[] args) { int[] A = {10, 15, 25}; int[] B = {1, 5, 20, 30}; Stack<Integer> st = new Stack<>(); for (int i = 0; i < A.length; i++) { st.push(A[i]); generateArrays(A, B, i, 0, st, false); st.clear(); } } static void generateArrays(int ar1[], int ar2[], int index_of_a, int index_of_b, Stack<Integer> st, boolean first) { if (index_of_a >= ar1.length || index_of_b >= ar2.length) { st.pop(); return; } // take from second if available if (!first) { for (int j = index_of_b; j < ar2.length; j++) { if (ar1[index_of_a] < ar2[j]) { st.push(ar2[j]); System.out.println(st); generateArrays(ar1, ar2, index_of_a + 1, j, st, true); } } } // take from first if available else if (first) { for (int i = index_of_a; i < ar1.length; i++) { if (ar1[i] > ar2[index_of_b]) { st.push(ar1[i]); generateArrays(ar1, ar2, i, index_of_a + 1, st, false); } } } st.pop(); }