Morgan Stanley Interview Question
Software DevelopersInterview Type: In-Person
public static ArrayList<String> find(List<String> input, int aI){
ArrayList<String> result = new ArrayList<>();
if(aI == input.size()) return result;
char[] charStr = input.get(aI).toCharArray();
if(aI == input.size()-1){
for(int i=0;i<charStr.length; i++){
result.add(""+charStr[i]);
}
return result;
}
for(int i=0;i<charStr.length; i++){
ArrayList<String> rest = find(input, aI+1);
for(String s : rest){
result.add(charStr[i] + s);
}
}
return result;
}
public static ArrayList<String> find(List<String> input, int aI){
ArrayList<String> result = new ArrayList<>();
if(aI == input.size()) return result;
char[] charStr = input.get(aI).toCharArray();
if(aI == input.size()-1){
for(int i=0;i<charStr.length; i++){
result.add(""+charStr[i]);
}
return result;
}
for(int i=0;i<charStr.length; i++){
ArrayList<String> rest = find(input, aI+1);
for(String s : rest){
result.add(charStr[i] + s);
}
}
return result;
}
void func(vector<string> &v,string &temp,int index,vector<string> &res,int n)
{
if(temp.length() == n)
{
res.push_back(temp);
return;
}
for(int i=0;i<n;++i)
{
string str = v[index];
temp.push_back(v[index][i]);
func(v,temp,index+1,res,n);
temp.pop_back();
}
}
int main() {
int n;
cin>>n;
vector<string> v;
for(int i=0;i<n;++i)
{
string temp;
cin>>temp;
v.push_back(temp);
}
string temp;
vector<string> res;
func(v,temp,0,res,n);
for(auto it : res)
cout<<it<<" ";
return 0;
}
void func(vector<string> &v,string &temp,int index,vector<string> &res,int n)
{
if(temp.length() == n)
{
res.push_back(temp);
return;
}
for(int i=0;i<n;++i)
{
string str = v[index];
temp.push_back(v[index][i]);
func(v,temp,index+1,res,n);
temp.pop_back();
}
}
int main() {
int n;
cin>>n;
vector<string> v;
for(int i=0;i<n;++i)
{
string temp;
cin>>temp;
v.push_back(temp);
}
string temp;
vector<string> res;
func(v,temp,0,res,n);
for(auto it : res)
cout<<it<<" ";
return 0;
}
void func(vector<string> &v,string &temp,int index,vector<string> &res,int n){
if(temp.length() == n){
res.push_back(temp);
return;
}
for(int i=0;i<n;++i){
string str = v[index];
temp.push_back(v[index][i]);
func(v,temp,index+1,res,n);
temp.pop_back();
}
}
int main() {
int n;
cin>>n;
vector<string> v;
for(int i=0;i<n;++i){
string temp;
cin>>temp;
v.push_back(temp);
}
string temp;
vector<string> res;
func(v,temp,0,res,n);
for(auto it : res)
cout<<it<<" ";
return 0;
}
{public class MultipleStringPermutation {
public static void main(String[] args) {
String str[] = {"abc","def","ghi"};
String s = "";
int i = 0, j= 0;
while(j < str[i].length() && j < str.length){
s += str[i].charAt(j);
i++;
if (i == str.length){
j++;
i=0;
//System.out.println(s);
permute(s, 0, s.length()-1);
s = "";
}
}
}
private static void permute(String str, int l, int r)
{
if (l == r)
System.out.println(str);
else
{
for (int i = l; i <= r; i++)
{
str = swap(str,l,i);
permute(str, l+1, r);
str = swap(str,l,i);
}
}
}
public static String swap(String a, int i, int j)
{
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i] ;
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}
}}
public class MultipleStirngPermutation {
public static void main(String[] args) {
String str[] = {"abc","def","ghi"};
String s = "";
int i = 0, j= 0;
while(j < str[i].length() && j < str.length){
s += str[i].charAt(j);
i++;
if (i == str.length){
j++;
i=0;
//System.out.println(s);
permute(s, 0, s.length()-1);
s = "";
}
}
}
private static void permute(String str, int l, int r)
{
if (l == r)
System.out.println(str);
else
{
for (int i = l; i <= r; i++)
{
str = swap(str,l,i);
permute(str, l+1, r);
str = swap(str,l,i);
}
}
}
public static String swap(String a, int i, int j)
{
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i] ;
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}
}
A simple recursive task.
1. If string is single - return its chars as an array
2. if we have N strings - get chars of the first string, for each char of the string combine it with solution of the rest of strings.
Javascript solution:
- md.xytop May 05, 2018