CareerCup

public List<String> combine(String m, String n) {
   List<String> result  = new ArrayList<>();
   helper(m,n,0,0,new StringBuilder(), result);
   return result;

}

public void helper(String m, String n, int i, int j, StringBuilder prefix, List<String> results ) {
  if(i+j >= m.length() + n.length()) {
     results.add(prefix.toString());
     return;
  }
  if(i<m.length()) {
      helper(m,n,i+1,j,prefix.append(m.charAt(i)),results);
     prefix.remove(prefix.size()-1);
   }
if(j<n.length()) {
      helper(m,n,i,j+1,prefix.append(n.charAt(j)),results);
     prefix.remove(prefix.size()-1);
   }
 return;
}

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 G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.

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




Interviewee's solution:

#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;
    }

int find(String s1, String s2, int i, int j, String out){
		if(i == s1.length() && j == s2.length())
			return 0;
		else if(i == s1.length()){
			out += s2.substring(j, s2.length());
			System.out.println(out);
			return 1;
		}
		else if(j == s2.length()){
			out += s1.substring(i, s1.length());
			System.out.println(out);
			return 1;
		}
		else{
			int re = find(s1, s2, i+1, j, out + s1.charAt(i)) + find(s1, s2, i, j+1, out + s2.charAt(j));
			return re;
		}
	}