Interview Question
Country: United States
Interview Type: Written Test
In not wrong,
I believe they are looking for a given a list of arrays, form sets which contains atleast one elements from each array
String a[] = {"1","2","3"};
String b[] = {"a","b","c","d"};
String c[] = {"i","ii","iii","iv","v"};
public class CartesianOfLists {
public static List<List> getCartesianOfLists(List<List> inputListOfLists) {
List<List> permutations = new ArrayList<List>();
for (List list : inputListOfLists) {
permutations = generatePermutations(permutations, list);
}
return permutations;
}
private static List<List> generatePermutations(List<List> permutations, List<String> list) {
List<List> newPermutations = new ArrayList<List>();
for (String str : list) {
if (permutations.isEmpty()) {
List tempList = new ArrayList();
tempList.add(str);
newPermutations.add(tempList);
} else {
for (List tempList : permutations) {
List innerList = new ArrayList();
innerList.addAll(tempList);
if (!innerList.contains(str)) {
innerList.add(str);
newPermutations.add(innerList);
}
}
}
}
return newPermutations;
}
}
I think problem is defined a little bit wrong. First of all if we talk about permutations - the order matters, so in your problem we are talking about subsets. For example if we have one array and we need to form all subsets of it array. You can whether take an element from array or not. if lenght of array if n, then you've got 2^n subsets and you can represent it like bit strings.
- glebstepanov1992 December 12, 2013000
001
010
011
100
101
110
111
You can form form subsets of each array and answer will be Cartesian product of theese sets.