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;
}

hakanserce
January 02, 2013 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;
}

hakanserce
January 02, 2013 @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 );
}
}
}
}

hakanserce
January 01, 2013 Used a slightly modified inorder 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;
}

hakanserce
January 01, 2013 Open Chat in New Window
@krbchd Thanks for the comment.
 hakanserce January 03, 2013