hakanserce
BAN USER@popoff As I mentioned in the answer above, the nested for loop part is actually O(n). The nested loop iterates as much as the number of digits. Note that having a nested loop does not always mean that we have O(n^2) execution time. This problem is a perfect example for this.
- hakanserce January 03, 2013Just use counting sort ( O(n) ). Then rearrange the number starting with the biggest one.
Note that the nested for loop below make a total of n iterations only. So the resulting code is O(n).
public int getLargestRearranged( int number ){
int[] digitCounts = new int[10];
int remainingDigits = number;
while( remainingDigits > 0 ){
int currentDigit = remainingDigits % 10;
remainingDigits /= 10;
digitCounts[currentDigit]++;
}
int rearrangedNumber = 0;
for( int i = 9; i >= 0; i-- ){
if( digitCounts[i] == 0 ) continue;
for( int j = 0; j < digitCounts[i]; j++ ){
rearrangedNumber *= 10;
rearrangedNumber += i;
}
}
return rearrangedNumber;
}
public List<Node> getOrderedNodes(Node rootNode) {
List<Node> result = new LinkedList<Node>();
Stack<Node> currentLevel = new Stack<Node>();
Stack<Node> nextLevel = new Stack<Node>();
currentLevel.push(rootNode);
boolean isLeftToRight = true;
while( !currentLevel.isEmpty() ){
Node currentNode = currentLevel.pop();
if( currentNode != null ){
result.add(currentNode);
if(isLeftToRight){
nextLevel.push(currentNode.getLeft());
nextLevel.push(currentNode.getRight());
}else{
nextLevel.push(currentNode.getRight());
nextLevel.push(currentNode.getLeft());
}
}
if(currentLevel.isEmpty()){
isLeftToRight = !isLeftToRight;
Stack<Node> temp = currentLevel;
currentLevel = nextLevel;
nextLevel = temp;
}
}
return result;
}
@ds can you please post some code. I can make comments on that.
- hakanserce January 01, 2013I think this code results in an infinite loop. Try with a tree with just a single node (root) for instance.
In the while loop the node is first popped then pushed everytime, so the stack will never be empty.
Good answer.
A few notes:
- it is interesting to note that the answer is just the Nth Fibonacci number
- code can be improved using memoization/dynamic programming etc
Managing (or actually emulating) call stack explicitly;
class StackFrame{
Node node;
boolean isRecursive;
public StackFrame( Node node, boolean isRecursive ){
this.node = node;
this.isRecursive = isRecursive;
}
}
public void printInOrder( Node root ){
Stack<StackFrame> callStack = new Stack<StackFrame>();
callStack.push( new StackFrame( root, true ));
while( !callStack.isEmpty() ){
StackFrame frame = callStack.pop();
Node node = frame.node;
if( node != null ){
if( frame.isRecursive ){
callStack.push( new StackFrame( node.right, true) );
callStack.push( new StackFrame( node, false) );
callStack.push( new StackFrame( node.left, true) );
}else{
System.out.println( node );
}
}
}
}
Used a slightly modified in-order traversal code to find the smallest value larger than or equal to m. Time complexity is avg: O(log n), worst: O(n)
public BSTNode findBestFit( BSTNode node, int m ){
if(node == null ) return null;
BSTNode result;
if( node.value >= m ){
result = findBestFit( node.left, m );
if( result == null ){
result = node;
}
}else{ //moveto right
result = findBestFit( node.right, m );
}
return result;
}
Repalinehchavez, SHOT 1500 NIGHT 5000 Call girls in Munirka Metro 9711794795 at Apple
Hi, I am Aline From New York USA. I am working as a Real estate rental agent in an Energy ...
Repgradyjvierra, Animator at Alliance Global Servies
Je suis Grady de Phoenix USA. Je travaille en tant que technicien de laboratoire clinique dans la société Samuels Men ...
@krbchd Thanks for the comment.
- hakanserce January 03, 2013