jerry
BAN USERWell, is the question not just about counting how many steps it takes to reach the 1 from the number given by following the sequence
public static int getlongestCollapsesequence(int n, int count){
System.out.print(n + " ");
if(n==1)
return count;
if(n%2 == 0)
return getlongestCollapsesequence(n/2, count++);
else
return getlongestCollapsesequence(3*n+1, count++);
}

jerry
April 17, 2017  Sort the array first using quick sort
 then you can use the following logic
public static void sum(int []array,int sum){
int start = 0,end=array.length1;
while(start<end){
if(array[start]+array[end]==sum)
{
System.out.println(array[start]+ ", "+array[end]);
start++;
end;
}
else if(array[start]+array[end] > sum){
end;
}
else if(array[start]+array[end] < sum){
start++;
}
}
}
public static void removeInterval(int []interval, int[]input){
ArrayList<Integer> result = new ArrayList<Integer>();
for(int i=0;i<interval.length;i=i+2){
if(interval[i] <input[0]){
result.add(interval[i]);
result.add(interval[i+1]);
}
else if(interval[i] >=input[1]){
result.add(interval[i]);
result.add(interval[i+1]);
}
}
System.out.println(result.toString());
}
 jerry July 13, 2013Algorithm for linear time is
1) consider a string for eg abaaba, we transform the string as #a#b#a#a#b#a#
2) Manacher's algorithm fills in a table P[i] which contains how far the palindrome centered at i extends for eg till Ci. Then we can take Ci as the new center and try to expand
for # a # b # a # a # b # a#
P[] 0 1 0
which shows that at we have palindrome of length 1 taking a as center, now we again start taking b as center as the lest and right character's don't match around #
for # a # b # a # a # b # a #
P[] 0 1 0 3 0 1 6 1 0 3 0 1 0
which shows that at we have palindrome of length 3 taking b as center, now we again start taking # as center and the longest palindrome is at P6
Algorithm for linear time is
1) consider a string for eg abaaba, we transform the string as #a#b#a#a#b#a#
2) Manacher's algorithm fills in a table P[i] which contains how far the palindrome centered at i extends for eg till Ci. Then we can take Ci as the new center and try to expand
for # a # b # a # a # b # a#
P[] 0 1 0
which shows that at we have palindrome of length 1 taking a as center, now we again start taking b as center as the lest and right character's don't match around #
for # a # b # a # a # b # a #
P[] 0 1 0 3 0 1 6 1 0 3 0 1 0
which shows that at we have palindrome of length 3 taking b as center, now we again start taking # as center
So it shows that at P6 we have longest palindrome. of length 6
'abaaba'
public static void permutation(String s) {
permutation("", s);
}
private static void permutation(String prefix, String s) {
int n = s.length();
if (n == 0)
System.out.println(prefix);
else {
for (int i = 0; i < n; i++) {
permutation(prefix + s.charAt(i),
s.substring(0, i) + s.substring(i + 1, n));
}
}
}

jerry
February 04, 2013 public static void listStructure(String path) {
listStructure(new File(path));
}
public static void listStructure(File file) {
if (file.isDirectory()) {
for (File f : file.listFiles()) {
if (f.isDirectory())
System.out.println(f.getAbsolutePath());
listStructure(f);
}
}
if (file.isFile()) {
System.out.println(file.getAbsolutePath());
}
}

jerry
January 26, 2013 public int LCA(int value1,int value2){
Node node1 = find(value1);
Node node2 = find(value2);
int depth1 = depth(value1);
int depth2 = depth(value2);
if(depth1>depth2)
{
while(depth1>depth2)
{
node1 = node1.getParent();
depth1;
}
}else if(depth2>depth1)
{
while(depth2>depth1)
{
node2 = node2.getParent();
depth2;
}
}
while(node1 != null node2!= null){
if( node1 == node2)
break;
node1 = node1.getParent();
node2 = node2.getParent();
}
return node1.getValue();
}

jerry
January 22, 2013 public NodeQueue bfs(Node traverseNode, int level) {
NodeQueue nodeQueue = new NodeQueue();
NodeQueue resultQueue = new NodeQueue();
traverseNode.setLevel(1);
nodeQueue.push(traverseNode);
resultQueue.push(traverseNode);
while (!nodeQueue.isEmpty()) {
traverseNode = nodeQueue.pop();
level = traverseNode.getLevel();
level++;
if (traverseNode.getLeft() != null) {
traverseNode.getLeft().setLevel(level);
nodeQueue.push(traverseNode.getLeft());
// resultQueue.push(traverseNode.getLeft());
}
if (traverseNode.getRight() != null) {
traverseNode.getRight().setLevel(level);
nodeQueue.push(traverseNode.getRight());
// resultQueue.push(traverseNode.getRight());
}
if(level%2==0){
if (traverseNode.getRight() != null) {
resultQueue.push(traverseNode.getRight());
}
if (traverseNode.getLeft() != null) {
resultQueue.push(traverseNode.getLeft());
}
}
else
{
if (traverseNode.getLeft() != null) {
resultQueue.push(traverseNode.getLeft());
}
if (traverseNode.getRight() != null) {
resultQueue.push(traverseNode.getRight());
}
}
}
return resultQueue;
}

jerry
October 22, 2012 public class Keypad {
public static final String[] keypad = {" ", " ", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"};
static StringBuffer s=new StringBuffer();
public void printAlphabets(int number){
int digit = number%10;
int i;
if(number == 0)
{
System.out.print(s.toString()+", ");
return;
}
String currentString = keypad[digit];
for(i = 0;i<currentString.length();i++){
s.append(currentString.charAt(i));
printAlphabets(number/10);
s.delete(s.length()1,s.length());
}
}
public static void main(String argv[]) {
Keypad key = new Keypad();
key.printAlphabets(410292);
}
}
public int search_KMP(char[] text, char[] word) {
int m = 0, i = 0;
int[] t = table_KMP(text);
while (m + i < text.length) {
if (text[m + i] == word[i]) {
if (i == word.length1) {
return m;
}
i = i + 1;
} else {
m = m + i  t[i];
if (t[i] > 1)
i = t[i];
else
i = 0;
}
}
return m;
}
public int[] table_KMP(char[] word) {
int t[] = new int[word.length];
t[0] = 1;
t[1] = 0;
int pos = 2, cnd = 0;
while (pos < word.length) {
if (word[pos  1] == word[cnd]) {
cnd += 1;
t[pos] = cnd;
pos += 1;
} else if (cnd > 0) {
cnd = t[cnd];
} else {
t[pos] = 0;
pos += 1;
}
}
return t;
}
public int occurence(int k,String text, String word){
int i,index = 0,position = 0;
for(i = 0;i<k;i++){
text = text.substring(index);
index = search_KMP(text.toCharArray(),word.toCharArray());
if(i != k1)
{
index = index +word.length();
}
position = position+index;
}
return position;
}
public int findNearest(double key) {
Node previousNode = null;
Node traverseNode = root;
int absValue;
float value;
while (traverseNode != null) {
if (key < traverseNode.getValue()) {
previousNode = traverseNode;
traverseNode = traverseNode.getLeft();
} else {
previousNode = traverseNode;
traverseNode = traverseNode.getRight();
}
if ((traverseNode == null)
 (key > previousNode.getValue() && key < traverseNode
.getValue())) {
break;
}
}
Double diffParent = Math.abs(previousNode.getValue() key);
Double diffNode = Math.abs(traverseNode.getValue() key);
if(diffParent <diffNode){
return previousNode.getValue();
}else
{
return traverseNode.getValue();
}
}
public int findNearest(double key) {
Node previousNode = null;
Node traverseNode = root;
int absValue;
float value;
while (traverseNode != null) {
if (key < traverseNode.getValue()) {
previousNode = traverseNode;
traverseNode = traverseNode.getLeft();
} else {
previousNode = traverseNode;
traverseNode = traverseNode.getRight();
}
if ((traverseNode == null)
 (key > previousNode.getValue() && key < traverseNode
.getValue())) {
break;
}
}
Double diffParent = Math.abs(previousNode.getValue() key);
Double diffNode = Math.abs(traverseNode.getValue() key);
if(diffParent <diffNode){
return previousNode.getValue();
}else
{
return traverseNode.getValue();
}
}

jerry
February 26, 2012 public void incrementNumber(int num[]) {
int[] result = new int[num.length];
int carry = 1;
for (int i = num.length  1; i >= 0; i) {
result[i] = num[i] + carry;
if (result[i] > 9) {
if (i == 0) {
result[i] = result[i] % 10;
result = incrementArray(result);
result[i] = 1;
} else {
result[i] = result[i] % 10;
carry = 1;
}
} else {
carry = 0;
}
}
for (int i = 0; i < result.length; i++) {
System.out.println(result[i] + " ");
}
}
public int[] incrementArray(int result[]) {
int[] newArray = new int[result.length + 1];
for (int i = result.length  1; i >= 0; i) {
newArray[i + 1] = result[i];
}
return newArray;
}
The filling of the cups with water need to be affected by the water left in the jug for the rest of cups .So after filling the water in cups at each level, we need to recalculate the water left in jug and the %of water to be filled in each cups as we go down
V =capacity of jug
v = capacity of cup
l = level
n = number of cups at that level
final_l = final level to which cups are to be filled for eg 5th level
initially
l = 1, n = 1;
%pernentage = (V  (l*n*v))/(final_l* final_l  l*n)
After filling the water to the cups at each level we can calculate the percentage of water to be filled in the cups at next level so that all the cups are covered, also store the value of % into an array
Open Chat in New Window
The solution is Morris Traversal i.e to do the inorder traversal without extra space, We just need to do inorder traversal using morris traversal till we find the median which can be n/2 for even count and (n1)/2 when count is odd
 jerry April 18, 2017