CareerCup

#include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    long factorial(long n){
        long fact = 1;
        for (long i = 1; i<= n; ++i)
            fact *= i;
        return fact;
    }

    void DFS(const string &s1, int m, int i,
    const string&s2, int n, int j,
    string path,vector<string> &ret){
        if(i==m &&j==n)  {
            ret.push_back(path);
            return;
        }
        if(i < m)  DFS(s1, m, i+1, s2, n, j, path+s1, ret);
        if(j < n)  DFS(s1, m, i, s2, n, j+1, path+s2[j], ret);
    }

    vector<string> combineTowStrings(const string &s1,const string &s2) {
        int m =s1.length(), n = s2.length();
        long count =factorial(m+n)/factorial(n)/factorial(m);
        cout <<"count:" << count << endl;
        vector<string> ret;
        DFS(s1, m, 0, s2,n, 0, "", ret);
        return ret;
    }

    int main() {
        vector<string> ret = combineTowStrings("AB","CDF");
        cout <<ret.size() << endl;
        for(string &s: ret)  cout << s << endl;
        return 0;

}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.

We provide ONE TO ONE courses that cover everything in an interview including
the latest interview questions categorized by companies,
algorithms,
SYSTEM DESIGN Courses(highly recommended for people interviewing with FLAG)
and mock interviews.

All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work.

Our students got offers from Google, Uber, Facebook, Amazon and other top companies after a few weeks of training.

Welcome to email us with any questions. Thanks for reading.

public class Main {

    public static void main(String[] args) {
        String s1 = "main"; //"abc";
        String s2 = "view"; //"de";

        List<String> res = new ArrayList<>();
        mergeStrings(s1, s2, 0, 0, "", res);

        System.out.println("Number of combinations: " + res.size());
        for (String s : res) {
            System.out.println(s);
        }
    }

    private static void mergeStrings(String s1, String s2, int pos1, int pos2, String curr, List<String> res) {
        if (pos1 == s1.length()) {
            res.add(curr + s2.substring(pos2));
            return;
        }

        if (pos2 == s2.length()) {
            res.add(curr + s1.substring(pos1));
            return;
        }
        mergeStrings(s1, s2, pos1 + 1, pos2, curr + s1.charAt(pos1), res);
        mergeStrings(s1, s2, pos1, pos2+1, curr + s2.charAt(pos2), res);
    }
}

This is anagram once two strings are concatenated.
So, simply add two strings and run anagram algorithm.
The complexity is (m +n) !

package algorithm;

import static java.lang.System.out;

public class Anagram {
public void anagram(String prefix, String word) {
if (word.length() <= 1) {
out.println(prefix + word);
return;
}

for (int i = 0; i < word.length(); i++) {
String before = word.substring(0, i); // letters before cur
String cur = word.substring(i, i + 1);
String after = word.substring(i + 1); // letters after cur
anagram(prefix + cur, before + after);
}
}

public static void main(String[] args) {
Anagram anagram = new Anagram();
String s1 = "...";
String s2 = "......";
anagram.anagram("", s1+s2);
}
}

from collections import deque
import math
s1 = 'abc'
s2 = '12'

def string_combine(s1, s2):
    s1 = deque(s1)
    s2 = deque(s2)
    s = deque()
    __str_combine(s1, s2, s)

def __str_combine(s1, s2, s):
    if len(s1) == 0 and len(s2) == 0:
        print(s)
    else:
        if len(s1) > 0:
            s.append(s1.popleft())
            __str_combine(s1, s2, s)
            s1.appendleft(s.pop())
        if len(s2) > 0:
            s.append(s2.popleft())
            __str_combine(s1, s2, s)
            s2.appendleft(s.pop())


def string_combination_count(s1, s2):
    # think m+n as slots 
    # and choosing positions for chars in min length string without order in those slots
    m = len(s1)
    n = len(s2)
    to_choose = min(m,n)
    slots = m+n
    return int(math.factorial(slots) / (math.factorial(to_choose) * math.factorial(slots - to_choose)))

string_combine(s1, s2)
print(string_combination_count(s1, s2))

here is a simple solution

package main

import (
	"bytes"
	"fmt"
)

func mergeStrings(s1, s2 string) string {
	var merged bytes.Buffer
	var i, j int
	for i < len(s1) && j < len(s2) {
		//fmt.Printf("i and j are %d, %d \n", i, j)
		if s1[i] < s2[j] {
			merged.WriteString(string(s1[i]))
			i += 1
		} else if s1[i] > s2[j] {
			merged.WriteString(string(s2[j]))
			j += 1
		} else {
			merged.WriteString(string(s1[i]))
			i += 1
			j += 1
		}
	}

	if i < len(s1) {
		for i < len(s1) {
			merged.WriteString(string(s1[i]))
			i += 1
		}
	}

	if j < len(s2) {
		for j < len(s2) {
			merged.WriteString(string(s2[j]))
			j += 1
		}
	}

	return merged.String()
}

func main() {
	str1 := "ace"
	str2 := "bdf"
	merged := mergeStrings(str1, str2)
	fmt.Printf("Merged str is %s", merged)
}

package main

import (
	"bytes"
	"fmt"
)

func mergeStrings(s1, s2 string) string {
	var merged bytes.Buffer
	var i, j int
	for i < len(s1) && j < len(s2) {
		//fmt.Printf("i and j are %d, %d \n", i, j)
		if s1[i] < s2[j] {
			merged.WriteString(string(s1[i]))
			i += 1
		} else if s1[i] > s2[j] {
			merged.WriteString(string(s2[j]))
			j += 1
		} else {
			merged.WriteString(string(s1[i]))
			i += 1
			j += 1
		}
	}

	if i < len(s1) {
		for i < len(s1) {
			merged.WriteString(string(s1[i]))
			i += 1
		}
	}

	if j < len(s2) {
		for j < len(s2) {
			merged.WriteString(string(s2[j]))
			j += 1
		}
	}

	return merged.String()
}

func main() {
	str1 := "ace"
	str2 := "bdf"
	merged := mergeStrings(str1, str2)
	fmt.Printf("Merged str is %s", merged)
}

typedef map<__int64, vector<std::string>> _subset_map;
void getMerges(const std::string& a, const std::string&b, const std::string& prefix, _subset_map& subsets, vector<std::string>& ret)
{
	if (a.size() == 0 && b.size() == 0)
	{
		ret.push_back(prefix);
		return;
	}
	__int64 key = a.size();
	key = (key << 32) | b.size();
	_subset_map::const_iterator f = subsets.find(key);
	const vector<std::string>* sub_vector;
	if (f == subsets.end())
	{
		vector<std::string>& sub = subsets[key];
		if(a.size()>0)
			getMerges(a.substr(1), b, std::string(1, a[0]), subsets, sub);
		if (b.size()>0)
			getMerges(a, b.substr(1), std::string(1, b[0]), subsets, sub);
		sub_vector = &sub;
	}
	else
	{
		sub_vector = &(f->second);
	}
	for (int i = 0, n = sub_vector->size(); i<n; i++)
		ret.push_back(prefix + sub_vector->at(i));
}
void getMerges(const std::string& a, const std::string& b, vector<std::string>& ret)
{
	_subset_map subsets;
	getMerges(a, b, "", subsets, ret);
}

you can simply reduce the problem to combinatorics solution.

e.g., how many ways a I can arrange m red and n blue balls.
Answer is (m+n)!/m!*n!

public class Main {

public static void main(String[] args) {
String s1 = "main"; //"abc";
String s2 = "view"; //"de";

List<String> res = new ArrayList<>();
mergeStrings(s1, s2, 0, 0, "", res);

System.out.println("Number of combinations: " + res.size());
for (String s : res) {
System.out.println(s);
}
}

private static void mergeStrings(String s1, String s2, int pos1, int pos2, String curr, List<String> res) {
if (pos1 == s1.length()) {
res.add(curr + s2.substring(pos2));
return;
}

if (pos2 == s2.length()) {
res.add(curr + s1.substring(pos1));
return;
}
mergeStrings(s1, s2, pos1 + 1, pos2, curr + s1.charAt(pos1), res);
mergeStrings(s1, s2, pos1, pos2+1, curr + s2.charAt(pos2), res);
}
}