Reverse a number in Java/Reverse an integer in Java
This is a well known program but quite frequently asked. Given an integer, reverse it. There are many ways to do that. And the ideal way is to use an extra variable and using a loop. The program is very simple, please find it below.
Looks like the climax of Ratatouille - back to school days. I tried solving the problem using a char[] but it almost took twice the time as this method. Used another method (which i am not proud of) too which was too heavy - Push to StringBuffer and call the reverse(). However, the internal implementation of both of my methods is the same.
Mostly these types of questions are targeted at C, C++. These will be asked to solve using simple memory locations. Life will become real miserable when they put a lot of conditions in place, like dont use extra memory, do this in O(1) etc., During those times, even the simplest of problems will look like giants and will take the left brains out of us. :)
Hi, when you fixed the two nodes in same path case, your code failed to common case like they only have common subpath. The solution I thought to fix it below:
public BinarySearchTree.Node findCommonParent(BinarySearchTree t, BinarySearchTree.Node node1, BinarySearchTree.Node node2){ TracePath pathTracer = new TracePath();
/** * If either of the nodes is root, then there is no common * parent */ if(node1.equals(t.getRoot()) || node2.equals(t.getRoot())){ return null; } //Using the path tracer, find the path of two nodes in 2*O(n) time. Stack path1 = trace(t, node1); Stack path2 = trace(t, node2);
//All that is left to do is to find the common parent now. Set firstPath = new HashSet(); for(BinarySearchTree.Node iNode:path1){ firstPath.add(iNode); } while(!path2.isEmpty()){ BinarySearchTree.Node currentNode = path2.pop(); if(firstPath.contains(currentNode)){ if(currentNode.value==n1.value || currentNode.value==n2.value){ return path2.peek(); } return currentNode; } } return null; }
5 comments:
Looks like the climax of Ratatouille - back to school days. I tried solving the problem using a char[] but it almost took twice the time as this method. Used another method (which i am not proud of) too which was too heavy - Push to StringBuffer and call the reverse(). However, the internal implementation of both of my methods is the same.
Mostly these types of questions are targeted at C, C++. These will be asked to solve using simple memory locations. Life will become real miserable when they put a lot of conditions in place, like dont use extra memory, do this in O(1) etc., During those times, even the simplest of problems will look like giants and will take the left brains out of us. :)
May be this can be approached this way too:
r = log num / log 10 ;
r = pow(10,r);
while(r)
{
printf(num/r);
num -= (num/r)*r;
r /= 10;
}
recursive method is best suitable for this .. It doesn't use any extra memory.
Hi, when you fixed the two nodes in same path case, your code failed to common case like they only have common subpath. The solution I thought to fix it below:
public BinarySearchTree.Node findCommonParent(BinarySearchTree t, BinarySearchTree.Node node1, BinarySearchTree.Node node2){
TracePath pathTracer = new TracePath();
/**
* If either of the nodes is root, then there is no common
* parent
*/
if(node1.equals(t.getRoot()) || node2.equals(t.getRoot())){
return null;
}
//Using the path tracer, find the path of two nodes in 2*O(n) time.
Stack path1 = trace(t, node1);
Stack path2 = trace(t, node2);
//All that is left to do is to find the common parent now.
Set firstPath = new HashSet();
for(BinarySearchTree.Node iNode:path1){
firstPath.add(iNode);
}
while(!path2.isEmpty()){
BinarySearchTree.Node currentNode = path2.pop();
if(firstPath.contains(currentNode)){
if(currentNode.value==n1.value || currentNode.value==n2.value){
return path2.peek();
}
return currentNode;
}
}
return null;
}
Let me know if you have any questions. Thank
Post a Comment