grandbora
BAN USERtest cases:
1) null ?
2) 1
3) 1-2
4) 1-(2-3)-4
4.a) 1-(2-3)-(4-5)
5) 1-(2-(3-4))-5
class Iterator
{
LinkedList linkedList;
Iterator: innerIterator = null;
public Iterator(LinkedList: linkedList){
this.linkedList = linkedList;
}
public Node[] toArray(){
Node[] nodeArray;
next = next();
if (next == null) return new Node[]();
do{
nodeArray.push(next);
next = next();
} while(next != null)
return nodeArray;
}
public Node next(){
Node next = null;
if( innerIterator != null){
next = getInnerNext();
if (next != null) return next;
clearInnerIterator();
}
next = linkedList.next();
if(next instanceOf LinkedList){
innerIterator = new Iterator(next);
return innerIterator.next();
}
return this.next;
}
private Node getInnerNext(){
innerIterator.next();
}
private void clearInnerIterator(){
innerIterator = null;
}
}
I gave it a go in javascript.
I assumed that this statement, which is given in an answer above, is correct:
´´´I think this question asks to divide the array in two equal halves with equal number of elements and equal sum that's why it says that array length is even´´´
This solution uses bruteforce and it is not optimized.
var source = [1,2,3,4,5,3,6,2];
splitToEqualValue(source);
function splitToEqualValue(source){
var halfSum = sum(source) / 2;
var equalParts = getVariants(source, source.length / 2).filter(function(variant){
return halfSum == sum(variant)
});
return equalParts; // a list that contains one of the equal pairs
}
function getVariants(source, length){
var variants = [];
if (length < 1 ) return [[]];
if (length > source.length ) length = source.length;
source.forEach(function(left, leftIndex){
var right = unpick(source,leftIndex);
var variantsOfRight = getVariants(right, length - 1).map(function(variant){
variant.unshift(left);
return variant;
})
// TODO Instead of bulk insert, do it one by one
// and if there is a duplicate(eg. same array different order dont add it)
variants = variants.concat(variantsOfRight);
})
return variants;
}
function sum(source){
return source.reduce(function(previousValue, currentValue, index, array){
return previousValue + currentValue;
});
}
function unpick(source, needleIndex){
return source.filter(function(elm, elmIndex){
return needleIndex != elmIndex;
})
}
Another js solution, does bruteforce, not optimal but works.
- grandbora January 16, 2014