## Google Interview Question for Software Engineer / Developers

• 4

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
3
of 3 vote

``````#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;

vector<vector<string> > sets;
vector<string> cs;

void print(int k) {

if(k == sets.size()) {
for(auto &x : cs) {
cout << x << " ";
}
cout << endl;
}
else {

for(int i = 0; i < sets[k].size(); i++) {
cs.push_back(sets[k][i]);
print(k+1);
cs.pop_back();
}

}

}

int main () {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif

sets = {{"quick", "slow"}, {"brown", "red"}, {"fox", "dog"}};

print(0);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

What is the time complexity?

Comment hidden because of low score. Click to expand.
2

O(A1 * A2 * ... * An) where A1 is the number of elements of the first set, etc

Comment hidden because of low score. Click to expand.
1
of 1 vote

Algo

call recursively for each position after adding every string in current position

``````//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
if(pos==n){print v;return;}
for i from 0 to list[pos].size()
v.push_back(list[pos][i])
print(pos+1,v);
v.pop_back();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Position {
int node;
int index;
}

void print(List<List<String>> input) {
if (input == null || input.size() == 0) {
return ;
}
int root = findNextList(input, 0);
if (root == -1) {
return ;
}
Position[] path = new Position[input.size()];
for (int i=0; i<input.size(); i++) {
path[i] = new Position();
}
dfs(input, root, path, 0);
}

int findNextList(List<List<String>> input, int start) {
for (; start < input.size(); start++) {
if (input.get(start).size() > 0) {
return start;
}
}
return -1;
}

void dfs(List<List<String>> input, int root, Position[] path, int k) {
for (int i=0; i<input.get(root).size(); i++) {
path[k].node = root;
path[k].index = i;
int next = findNextList(input, root+1);
if (next == -1) {
for (int j=0; j<=k; j++) {
System.out.print(input.get(path[j].node).get(path[j].index) + " ");
}
System.out.println();
} else {
dfs(input, next, path, k+1);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void wordPerm(ArrayList<ArrayList<String>> lists) {

wordPermUtil(lists,0,"");

}

private static void wordPermUtil(ArrayList<ArrayList<String>> lists, int depth, String cur) {
if (depth  == lists.size()) {
System.out.println(cur.trim());
return;
}

for (int i = 0; i < lists.get(depth).size(); i++) {
wordPermUtil(lists, depth + 1, cur + " " + lists.get(depth).get(i));
}
}``````

Test:

``````public static void main(String[] args) {
ArrayList<ArrayList<String>> lists = new ArrayList<ArrayList<String>>();
ArrayList<String> list1 = new ArrayList<String>(Arrays.asList("quick","slow");
ArrayList<String> list2 = new ArrayList<String>(Arrays.asList("brown","red"));
ArrayList<String> list3 = new ArrayList<String>(Arrays.asList("fox","dog"));

wordPerm(lists);
}``````

Comment hidden because of low score. Click to expand.
0

You will need to remove last inserted element after the recursive call in your for loop.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Using backtracking.

``````void printRec(String[][] arrays, int index, String[] res){

if( index >= arrays.length ){
System.out.println( Arrays.toString(res) );
return;
}

String[] cur = arrays[index];

for( int i = 0; i < cur.length; i++ ){
res[index] = cur[i];
printRec(arrays, index+1, res);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````input_list = [['quick', 'slow'], ['brown', 'red'], ['fox', 'dog']]

def main(str, input):
if(input):
items = input[0]
for item in items:
main(str + ' ' + item, input[1:])
else:
print str

if __name__ == '__main__':
main('', input_list)``````

Comment hidden because of low score. Click to expand.
0

Man what does if __name == '__main__':
...
do?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a non-recursive solution. The complexity is of course O(N1 x N2 x ... x Nk) where Ni is the number of elements in set i.

``````public static void main(String[] args) {
String[][] sets = new String[][] {{"quick", "slow"}, {"brown", "red"}, {"fox", "dog"}};
int[] state = new int[sets.length];
int p = 0;
while (true) {
for (int i = 0; i < state.length; i++) {
System.out.print(sets[i][state[i]] + " ");
}
System.out.println();
state[p]++;
while( state[p] == sets[p].length) {
state[p] = 0;
p++;
if (p == sets.length) return;
state[p]++;
}
p = 0;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo

call recursively for each position after adding every string in current position

``````//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
if(pos==n){print v;return;}
for i from 0 to list[pos].size()
v.push_back(list[pos][i])
print(pos+1,v);
v.pop_back();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo

call recursively for each position after adding every string in current position

``````//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
if(pos==n){print v;return;}
for i from 0 to list[pos].size()
v.push_back(list[pos][i])
print(pos+1,v);
v.pop_back();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo

call recursively for each position after adding every string in current position

``````//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
if(pos==n){print v;return;}
for i from 0 to list[pos].size()
v.push_back(list[pos][i])
print(pos+1,v);
v.pop_back();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo

call recursively for each position after adding every string in current position

``````//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
if(pos==n){print v;return;}
for i from 0 to list[pos].size()
v.push_back(list[pos][i])
print(pos+1,v);
v.pop_back();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo

call recursively for each position after adding every string in current position

``````//vector<vector<string>> list
//n=list.size()
print(int pos,vector<string> v)
{
if(pos==n){print v;return;}
for i from 0 to list[pos].size()
v.push_back(list[pos][i])
print(pos+1,v);
v.pop_back();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public List<string> Combinations(List<List<string>> li)
{
List<string> combinationlist = new List<string>(); ;
StringBuilder sb = new StringBuilder();
int l;
int i;

for(l = 0; l < (li[0].Count); l++)
{
for(i = 1; i < (li.Count); i++)
{
for (int j = 0; j < (li[i].Count); j++)
{
sb.Append((li[0])[l].ToString());
sb.Append(" ");
sb.Append((li[i])[j].ToString());
sb.Clear();
}
}
}
return combinationlist;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}

public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}

ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}

public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}

ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}

public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}

ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}

public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}

ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}

public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}

ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}

public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}

ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}

public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}

ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}

public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}

ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}

public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}

ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void WordPerm(ArrayList<ArrayList<String>> lists)
{
WordPermHelper(lists, 0, "");
}

public static void WordPermHelper(ArrayList<ArrayList<String>> lists, int level, String curLevelString)
{
if (level >= lists.size()) {
System.out.println(curLevelString);
return;
}

ArrayList<String> curList = lists.get(level);
String helperStr = "";
for (int curWordNdx = 0; curWordNdx < curList.size(); curWordNdx++) {
helperStr = curLevelString + curList.get(curWordNdx) + ",";
WordPermHelper(lists, level + 1, helperStr);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import Control.Monad
import Data.List

ioAction :: [[String]] -> IO ()
ioAction input = forM_ (sequence input ) \$ putStrLn . intercalate " "

-- Test
main = ioAction [["quick","slow"],["brown","red"],["fox","dog"]]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

void comb(vector<vector<string> > dict, int s, vector<string> tmp )
{
if(s==dict.size())
{
for(int i=0; i<tmp.size(); i++)
cout<<tmp[i]<<" ";
cout<<"\n";
return;
}
for(int j=0; j<dict[s].size(); j++)
{
tmp.push_back(dict[s][j]);
comb(dict, s+1, tmp);
tmp.pop_back();
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

We can implement this recursively:

``````def combinations(item_lists):
"""Returns a list with all possible lists generated by choosing
one item from each list in item_lists"""
if not item_lists:
return [[]]
combination_list = []
for item in item_lists[0]:
for combination in combinations(item_lists[1:]):
combination_list.append([item] + combination)
return combination_list``````

Having written this function, we just have to call it and print the values. E.g.:

``````item_lists = [['quick','slow'],['brown','red'],['fox','dog']]
for combination in combinations(item_lists):
for s in combination:
print s + ' ',
print``````

Output:

``````quick  brown  fox
quick  brown  dog
quick  red  fox
quick  red  dog
slow  brown  fox
slow  brown  dog
slow  red  fox
slow  red  dog``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

String s1[]={"1","2"};
String s2[]={"A","B"};
String s3[]={"X","Z"};
for (int i = 0; i < s1.length; i++) {
for (int j = 0; j < s2.length; j++) {
for (int k = 0; k < s3.length; k++) {
System.out.println(s1[i]+"-"+s2[j]+"-"+s3[k]);
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

String s1[]={"1","2"};
String s2[]={"A","B"};
String s3[]={"X","Z"};
for (int i = 0; i < s1.length; i++) {
for (int j = 0; j < s2.length; j++) {
for (int k = 0; k < s3.length; k++) {
System.out.println(s1[i]+"-"+s2[j]+"-"+s3[k]);
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

void printAllCombination(int index, vector<vector<string> > &list,vector<string> &strs)
{
if(index==list.size())
{
for(int i=0;i<strs.size();i++)
cout<<strs[i]<<"  ";
cout<<"\n";
return;
}
for(int i=0;i<list[index].size();i++)
{
strs.push_back(list[index][i]);
printAllCombination(index+1,list,strs);
strs.pop_back();
}
}
int main()
{
vector<vector<string> > list;
vector<string> v;
v.push_back("quick");v.push_back("slow");v.push_back("fast"); list.push_back(v); v.clear();
v.push_back("brown");v.push_back("red"); list.push_back(v); v.clear();
v.push_back("fox");v.push_back("dog");v.push_back("tiger");v.push_back("elephant"); list.push_back(v); v.clear();

printAllCombination(0,list,v);``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution
{
public:
list<list<string> > comb(list<list<string> > &input)
{
list<list<string> > ans,abl;
if (input.empty()) return ans;
list<string> last=input.back();
input.pop_back();
abl=comb(input);
for (list<string>::iterator ls=last.begin();ls!=last.end();++ls)
{
for (list<list<string> >::iterator lls=abl.begin();lls!=abl.end();++lls)
{
list<string> tmp=*lls;
tmp.push_back(*ls);
ans.push_back(tmp);
}
if (abl.empty())
{
list<string> tmp;
tmp.push_back(*ls);
ans.push_back(tmp);
}
}
return ans;
}
};``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
void comb(vector<vector<string> > dict, int s, vector<string> tmp )
{
if(s==dict.size())
{
for(int i=0; i<tmp.size(); i++)
cout<<tmp[i]<<" ";
cout<<"\n";
return;
}
for(int j=0; j<dict[s].size(); j++)
{
tmp.push_back(dict[s][j]);
comb(dict, s+1, tmp);
tmp.pop_back();
}
}
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void comb(vector<vector<string> > dict, int s, vector<string> tmp )
{
if(s==dict.size())
{
for(int i=0; i<tmp.size(); i++)
cout<<tmp[i]<<" ";
cout<<"\n";
return;
}
for(int j=0; j<dict[s].size(); j++)
{
tmp.push_back(dict[s][j]);
comb(dict, s+1, tmp);
tmp.pop_back();
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
#include<vector>
#include<string>

using namespace std;

void comb(vector<vector<string> > dict, int s, vector<string> tmp )
{
if(s==dict.size())
{
for(int i=0; i<tmp.size(); i++)
cout<<tmp[i]<<" ";
cout<<"\n";
return;
}
for(int j=0; j<dict[s].size(); j++)
{
tmp.push_back(dict[s][j]);
comb(dict, s+1, tmp);
tmp.pop_back();
}
}

int main()
{
vector<vector<string> > dict;
vector<string> tmp;
tmp.push_back("quick");
tmp.push_back("slow");
dict.push_back(tmp);
tmp.clear();
tmp.push_back("brown");
tmp.push_back("red");
dict.push_back(tmp);
tmp.clear();
tmp.push_back("fox");
tmp.push_back("dog");
dict.push_back(tmp);
tmp.clear();
int s = 0;
vector<int> l;
for(int i=0; i<dict.size(); i++)
l.push_back(0);

int j=0;
vector<string>  temp;
comb(dict, s , temp);

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

We recurse to N levels, where N is the number of lists of strings. On each level we iterate through all strings in current level list, store its index in int[] array and recurse further. Next level will fill it's own index with its next word. When we came to the next after last level - we have the indexes array filled with indexes of words in matching lists - we just iterate through them and print matching words.
When recursion goes back, the matching index in indexes array is overwritten with next word.

This has O(1) size complexity and O(M^N) time complexity where M is the largest number of words in lists and N is the number of lists.

O(1) size complexity is a big win as almost all solutions, that I see here, use strings concatenations, that would produce lots of garbage

``````public static void print(String[][] strings) {
permutate (strings, new int[strings.length], 0);
}

public static void permutate (String[][] strings, int[] indexes, int level) {
if (level >= strings.length) {
// we came to end, let's print the string
for (int i = 0; i < strings.length; i++) {
System.out.print(strings[i][indexes[i]]);
System.out.print(" ");
}
System.out.println();
return;
}
for (int i = 0; i < strings[level].length; i++) {
indexes[level] = i;
permutate(strings, indexes, level + 1);
}
}

public static void main(String[] args) {
String[][] strings = {{"quick", "slow"}, {"brown", "red"}, {"fox", "dog"}};
print(strings);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````class Solution_ListComb {
public:
void PrintListComb(const vector<vector<string> >& List) {
vector<string> curr;
dfs(List, curr, 0, List.size());
}

void dfs(const vector<vector<string> >& List, vector<string>& curr, int k, int n){
if (k == n) {
for (string str : curr)
cout << str << " ";
cout << endl;
return;
}

for (auto word : List[k]) {
curr.push_back(word);
dfs(List, curr, k + 1, n);
curr.pop_back();
}
}
};``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>

vector<vector<string> > listE; vector<string> nodeE;

char * itos(int a){char *p=new char;sprintf(p,"%d",a);return p;}

void test(int maxC,string s,unsigned int k)
{
if(s.size()==k){cout<<"\n\t\t String::"<<s;return;}
for(int ii=0;ii<maxC;ii++)
test(maxC,s+itos(ii),k);

}

void recur(int index,string s1,bool flag,unsigned int maxS)
{
//cout<<"\n"<<"\t Si size::"<<s1.size()<<"\t maxS::"<<maxS<<"\tString:"<<s1;
if(s1.size()==maxS && flag){cout<<"\n\t\t Inner ::"<<s1 ;return;}
if(s1.size()==maxS && !flag)
{
cout<<"\n Outter-->::"<<s1;
//for(unsigned int ii=0;ii<2;ii++)
{
s1="";
test(2,s1,4);
}
return;
}
for(unsigned int ii=0;ii<maxS;ii++)
{
//cout<<"\nS::"<<s1;
if(s1.find(itos(ii))!=string::npos)continue;
recur(index+1,s1+itos(ii),flag,maxS);
}
}

int main()
{

//[[quick, slow], [brown, red], [fox, dog]]
string a; nodeE.clear();
a="quick";nodeE.push_back(a);
a="slow";nodeE.push_back(a);
listE.push_back(nodeE);

nodeE.clear();
a="brown";nodeE.push_back(a);
a="red";nodeE.push_back(a);
listE.push_back(nodeE);

nodeE.clear();
a="brown";nodeE.push_back(a);
a="red";nodeE.push_back(a);
listE.push_back(nodeE);

nodeE.clear();
a="fox";nodeE.push_back(a);
a="dog";nodeE.push_back(a);
listE.push_back(nodeE);

recur(0,"",false,listE.size());
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

def main():
sets= [['quick', 'slow'], ['brown', 'red'], ['fox', 'dog']]

stringPrint(sets,0)

def stringPrint(sets,k):
if k==len(sets):
print words
else:
for _w in sets[k]:
words.append(_w)
stringPrint(sets,k+1)
words.pop()

Comment hidden because of low score. Click to expand.
0
of 0 vote

def main():
sets= [['quick', 'slow'], ['brown', 'red'], ['fox', 'dog']]

stringPrint(sets,0)

def stringPrint(sets,k):
if k==len(sets):
print words
else:
for _w in sets[k]:
words.append(_w)
stringPrint(sets,k+1)
words.pop()

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````comb(inputList, new ArrayList<String>(), 0);

public void comb(List<List<String>> list, List<String> res , int k ) {

if(k == list.size()) {
System.out.println(res);
// res.clear();
return;
}

List<String> subList = list.get(k);
for(int i =0 ; i< subList.size(); i++) {
comb(list, res, k+1);
res.remove(subList.get(i));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#!/usr/bin/python
def combinations(a,list2dstring):
if isASolution(a, list2dstring):
processSolution(a)
else:
nxtCandidates = constructCandidates(a, list2dstring)
for candidate in nxtCandidates:
a += [candidate]
combinations(a, list2dstring)
a.pop()
def isASolution(a, list2dstring):
return len(a) == len(list2dstring)

def processSolution(a):
print " ".join(a)

def constructCandidates(a, list2dstring):
return list2dstring[len(a)]

combinations([], [['quick', 'slow'], ['brown', 'red'], ['fox', 'dog']])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hope I can get a coding problem as simple as this one tomorrow

``````#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<algorithm>
#include<climits>
using namespace std;
void dfs(vector<string>&ret,vector<string> &tmp,vector<vector<string>>&input,int cur){
if(cur==input.size()){
string str=tmp[0];
for(int i=1;i<tmp.size();i++)
str+=" "+tmp[i];
ret.push_back(str);
}else{
for(int i=0;i<input[cur].size();i++){
tmp.push_back(input[cur][i]);
dfs(ret,tmp,input,cur+1);
tmp.pop_back();
}
}
}
vector<string>com(vector<vector<string>>&input){
vector<string>ret,tmp;
if(input.empty())
return ret;
dfs(ret,tmp,input,0);
return ret;
}
int main(){
vector<vector<string>>input;
vector<string>v1,v2,v3;
v1.push_back("a1");
v1.push_back("a1");
v2.push_back("b1");
v2.push_back("b2");
v3.push_back("c1");
v3.push_back("c2");
input.push_back(v1);
input.push_back(v2);
input.push_back(v3);
vector<string>ret=com(input);
for(int i=0;i<ret.size();i++)
cout<<ret[i]<<endl;
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def print_combinations_cheating(word_lists):
import itertools
for t in itertools.product(*word_lists):
print " ".join(t)

def print_combinations_generator(word_lists):
result = [[]]
for words in word_lists:
result = [x+[y] for x in result for y in words]
for combination in result:
print " ".join(combination)

def print_combinations(word_lists):
combinations = [[]]
for words in word_lists:
new_combinations = []
for L in combinations:
for word in words:
new_combinations.append(L + [word])
combinations = new_combinations

for combination in combinations:
print " ".join(combination)

print_combinations([["quick", "slow"], ["brown", "red"], ["fox", "dog"]])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````var findCombinations = (function () {
var res;

function getCombinations(list, current, index, el) {
if (index === list.length) {
return res.push(current.slice());
}
for (var i = 0; i < list[el].length; i += 1) {
current[index] = list[el][i];
getCombinations(list, current, index + 1, el + 1);
}
}

return function (list) {
res = [];
getCombinations(list, [], 0, 0);
return res;
};
}());``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Too few different codes. Must add my own implementation on C#:

``````static IEnumerable<string[]> AllCombinations(string[][] lists)
{
long cnt = lists.Aggregate(1L, (curr, list) => curr * list.Length);
{
string[] next = new string[lists.Length];
for (int i = 0; i < lists.Length; ++i)
{
next[i] = lists[i][m % lists[i].Length];
m /= lists[i].Length;
}
yield return next;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my version. The complexity is O(length(L1)xlength(L2)x...). Still looking for a better one. Probably there is something better and with less memory usage but mine is easy to read plus using new Java 8 functionality.

``````public class StringCombinations {

public static void printStringCombinations(List<List<String>> setList) {
}

private static void printAndCreateStringCombination(List<List<String>> setList, List<String> combination) {
if (setList.isEmpty()) {
printCombination(combination);
} else {
List<String> set = setList.get(0);

for (String s : set) {
printAndCreateStringCombination(setList.subList(1, setList.size()), newCombination);
}
}
}

private static void printCombination(List<String> combination) {
StringJoiner stringJoiner = new StringJoiner(",");

for (String s : combination) {
}

System.out.println("[" + stringJoiner.toString() + "]");
}

public static void main (String[] args) {

printStringCombinations(setList);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class RedBrownFox {
String[][] db ={{"red", "brown"},{"fox", "dog"},{"jumps","runs"}};

void printPerm(String sb, int n) {
if(db.length<=n) {
System.out.println(sb);
return ;
}
for(int i=0; i<db[n].length; i++) {
printPerm(sb+db[n][i], n+1);
}
}

public static void main(String[] args) {
RedBrownFox r = new RedBrownFox();
r.printPerm("", 0);
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a global int[] to restore the state. And use recursion to traverse them. It is quite similar as 8 queens game.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is another Python implementation using itertools:

``````def combinations(listoflists):
import itertools
for elements in list(itertools.product(*listoflists)):
print ' '.join(elements)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static void PrintAll(List<List<String>> in, String comb, int depth)
{
if (depth == in.size()) {
System.out.println(comb);
}
else {
List<String> lst = in.get(depth);
for (String s : lst) {
PrintAll(in, comb + ' ' + s, depth+1);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package p1;

import java.util.ArrayList;
import java.util.List;

public class ListExample
{
public static void main(final String[] args)
{
List<List<List>> sentences = new ArrayList<List<List>>();

List<List> each_sentence = new ArrayList<List>();

ArrayList<String> iob = new ArrayList<String> ();
ArrayList<String> pos = new ArrayList<String> ();
ArrayList<String> word = new ArrayList<String> ();

int i=0,j=0,k=0,l=0;
perm(sentences,i,j,k,l);
}
//	System.out.println(sentences.get(0).get(2).get(0));
public static void perm(List<List<List>> sentences, int i,int j,int k, int l){

System.out.print(sentences.get(0).get(i).get(j)+" ");
System.out.print(sentences.get(0).get(i+1).get(k)+" ");
System.out.print(sentences.get(0).get(i+2).get(l)+" ");
l=l+1;
if(l==2)
{
l=0;
k=k+1;
}
if(k==2)
{
k=0;
j=j+1;
}
if(j==2)
{
return;
}
System.out.println();

perm(sentences,i,j,k,l);

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Another solution in Python with O(N1 * N2 * ... * Nk), where Nk is a number of elements in list number k.

``````def combine(input_list, words=None):
if words is None:
words = []
if input_list is None:
print ' '.join(words)
return
for word in input_list[0]:
combine(input_list[1:] if len(input_list) > 1 else None, words + [word])

combine([('quick', 'slow'), ('brown', 'red'), ('fox', 'dog')])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void recPrintLists(vector < vector < string >> vec , string prefix) {
if (vec.size() == 0) {
cout << prefix + "\n";
return;
}
vector < vector < string >> nextVector(&vec[0] + 1, &vec[0] + vec.size());
for (int i = 0; i < vec[0].size(); i++) {
string newPreFix = prefix + vec[0][i] + " ";
recPrintLists(nextVector , newPreFix);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class MultiArrayPermutation {

public static void main(String[] args) {
solveMultiPerms2();
}

public static void solveMultiPerms2() {
String[][] sets = new String[][] {
{ "quick", "slow" },
{ "brown", "red" },
{ "fox", "dog" }
};

List<List<String>> r = new ArrayList<List<String>>();

printLists(r);
}

private static void printLists(List<List<String>> r) {
for (List<String> list : r) {
for (String string : list) {
System.out.print(string + " ");
}
System.out.println();
}
}

private static void backtrack(List<List<String>> strs, String[][] sets, LinkedList<String> list, int start) {
if (start == sets.length) {
} else if (start < sets.length) {
for (int i = 0; i < sets[start].length; i++) {
backtrack(strs, sets, list, start + 1);
list.removeLast();
}
}
}
}
/*
output:
quick brown fox
quick brown dog
quick red fox
quick red dog
slow brown fox
slow brown dog
slow red fox
slow red dog
*/``````

Comment hidden because of low score. Click to expand.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.