Interview Question for Developer Program Engineers
- -1of 1 vote
AnswersI realized this algorithm for generating combinations. It works in the following way, if we have the input:
- pasquale.restaino1992 July 11, 2015 in United States
[A, B, C]
The combinations will be
[A], [B], [C]. [A, B], [A, C], [B, C], [A, B, C].
While if we have in input:
[1,1,2,3]
The combinations will be:
[1], [2], [3], [4], [1,2], [1,3], [2,3 ], [1,1,2,3].
However, this algorithm has a running time of good only when the input is a list of size 4, if the list is of size 5 or more (when there are 5 different elements ( for example 80 A, 150 B , 80 C , 30 D , 20 E)) the program stops and gives me java.lang.OutOfMemory (I increased the memory for in java). One problem could be the fact that I have used LinkedList, but I'm not sure.
Is there a better solution?
private List<Elemento> combinazioneMassima = new ArrayList<>();
private Log logger = LogFactory.getLog(Combinazioni3.class);
public Combinazioni3(List<Elemento> generaCombinazioneMassima) {
this.combinazioneMassima = generaCombinazioneMassima;
}
public void combine() {
this.findAllCombinations(combinazioneMassima);
}
private static class Node{
int lastIndex = 0;
List<Elemento> currentList;
public Node(int lastIndex, List<Elemento> list) {
this.lastIndex = lastIndex;
this.currentList = list;
}
public Node(Node n) {
this.lastIndex = n.lastIndex;
this.currentList = new ArrayList<Elemento>(n.currentList);
}
}
public void findAllCombinations(List<Elemento> combinazioni) {
Date dataInizio = new Date();
List<List<Elemento>> resultList = new ArrayList<List<Elemento>>();
LinkedList<Node> queue = new LinkedList<Node>();
int n = combinazioni.size();
ArrayList<Elemento> temp = new ArrayList<Elemento>();
temp.add(combinazioni.get(0));
queue.add(new Node(0, temp));
// add all different integers to the queue once.
for(int i=1;i<n;++i) {
if(combinazioni.get(i-1) == combinazioni.get(i)) continue;
temp = new ArrayList<Elemento>();
temp.add(combinazioni.get(i));
queue.add(new Node(i, temp));
}
// do bfs until we have no elements
while(!queue.isEmpty()) {
Node node = queue.remove();
if(node.lastIndex+1 < n) {
Node newNode = new Node(node);
newNode.lastIndex = node.lastIndex+1;
newNode.currentList.add(combinazioni.get(node.lastIndex+1));
queue.add(newNode);
}
for(int i=node.lastIndex+2;i<n;++i) {
if(combinazioni.get(i-1) == combinazioni.get(i)) continue;
// create a copy and add extra integer
Node newNode = new Node(node);
newNode.lastIndex = i;
newNode.currentList.add(combinazioni.get(i));
queue.add(newNode);
}
GestoreRegole gestoreRegole = new GestoreRegole();
gestoreRegole.esegui(node.currentList);
}
}| Report Duplicate | Flag | PURGE
Developer Program Engineer Algorithm