CareerCup

def weave_arrays(array1, array2):
    right = deque()
    left = deque()
    for item in array1:
        right.append(item)
    for item in array2:
        left.append(item)
    prefix, results = deque(), []
    weave(right, left, prefix, results)
    for q in results:
        print(q)


def weave(left, right, prefix, results):
    if not len(left) or not len(right):
        result = deepcopy(prefix)
        result.extend(left)
        result.extend(right)
        results.append(result)
        return
    left_head = left.popleft()
    prefix.append(left_head)
    weave(left, right, prefix, results)
    left.appendleft(left_head)
    prefix.pop()
    right_head = right.popleft()
    prefix.append(right_head)
    weave(left, right, prefix, results)
    right.appendleft(right_head)
    prefix.pop()

The algorithm required here is weaving 2 lists. Consider if you have to weave [1, 2] and [3, 4] together. You can get all the permutations by recursively weaving [2] and [3, 4] prefixed with one and then recursively weaving [1, 2] and [4] prefixed with 3

val l1 = List('a') //> l1 : List[Char] = List(a)
val l2 = List('b') //> l2 : List[Char] = List(b)
val l3 =List('a', 'b') //> l3 : List[Char] = List(a, b)
val l4 =List('d') //> l4 : List[Char] = List(d)
def f (ls:List[Char], rs:List[Char]):List[List[Char]] = (ls, rs) match {
case (Nil,_) => rs::Nil
case (_,Nil) => ls::Nil
case (x::xs, y::ys) => (f(xs,rs) map (word => x::word)) ++ (f(ls,ys) map (word => y::word))
} //> f: (ls: List[Char], rs: List[Char])List[List[Char]]

f(l1,l2) //> res0: List[List[Char]] = List(List(a, b), List(b, a))
f(l3,l4) //> res1: List[List[Char]] = List(List(a, b, d), List(a, d, b), List(d, a, b))

Javascript solution

function perm(str1, str2, newArr, m, n, i) {

	// Base case: If all characters of str1 and str2 have been
	// included in output string, then print the output strin
	if (m == 0 && n == 0) {
		console.log(newArr)
		return;// base condition
	}

	// If some characters of str1 are left to be included, then
	// include the first character from the remaining characters
	// and recur for rest
	if (m !== 0) {
		newArr[i] = str1.charAt(0);
		perm(str1.substring(1), str2, newArr, m - 1, n, i + 1);
	}

	// If some characters of str2 are left to be included, then
	// include the first character from the remaining characters
	// and recur for rest
	if (n !== 0) {
		newArr[i] = str2.charAt(0);
		perm(str1, str2.substring(1), newArr, m, n - 1, i + 1);
	}
}

var str1 = "ab", str2 = "cd", i = 0;
perm(str1, str2, [], str1.length, str2.length, i);