nj
BAN USERI'm assuming you cannot take any extra space. The question is intended to solve the problem of converting the linked list into a tree. Otherwise, the problem is trivial if at all. You might as well build a RedBlack BST by feeding it elements in the sequential traversal of the Linked list.
- nj August 26, 2012Here is a recursive solution, obviously iterative should be preferred.
public static String eraseCouples(StringBuffer input, boolean zeroStreak)
{
if(input.length()>=2&&input.charAt(0)=='0'&&input.charAt(1)=='0')
if(input.charAt(2)!='0'&&!zeroStreak)
return eraseCouples(input.delete(0, 2), false);
else
return input.charAt(0)+ eraseCouples(input.deleteCharAt(0), true);
else if(input.length()>0)
return input.charAt(0)+ eraseCouples(input.deleteCharAt(0), false);
else return "";
}
public static void printJSON(String input, StringBuffer spaces, boolean useSpaces)
{
char printChar= input.charAt(0);
System.out.print(useSpaces?spaces.toString()+printChar:printChar);
if(input.length()<=1)
return;
useSpaces= true;
switch(printChar)
{
case ',':
System.out.print("\b\n");
break;
case ':' :
useSpaces= input.charAt(1)=='{';
if(useSpaces)
System.out.println();
break;
case '{':
System.out.println();
spaces= spaces.append(" ");
break;
case '}':
System.out.println();
spaces= spaces.length()>0?spaces.deleteCharAt(0):spaces;
break;
default:
useSpaces= input.charAt(1)=='}';
if(useSpaces)
System.out.println();
}
printJSON(input.substring(1, input.length()), spaces, useSpaces);
}
Here is the implementation of DoublyLinkedList:
import java.io.*;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author Nikhil Jain
*/
public class DoublyLinkedList {
public static class Node
{
int data;
Node prev, next;
public Node(int data)
{
this.data= data;
}
public Node()
{
this.data= Integer.MIN_VALUE;
}
public void add(Node n)
{
if(next==null)
{
next= n;
next.prev= this;
}
else
next.add(n);
}
@Override
public String toString()
{
return ""+data+(next!=null?","+next.toString():"");
}
public String toStringBST()
{
StringBuffer ret= new StringBuffer();
if(prev!=null)
ret.append(prev.toStringBST()+",");
ret.append(data+(next!=null?",":""));
if(next!=null)
ret.append(next.toStringBST());
return ret.toString();
}
}
public Node head;
public DoublyLinkedList()
{
this.head= new Node(Integer.MIN_VALUE);
}
public void add(int data)
{
head.add(new Node(data));
}
public static DoublyLinkedList getList(String filename)
throws FileNotFoundException, IOException
{
BufferedReader br= new BufferedReader(new InputStreamReader( new FileInputStream(new File(filename))));
String[] arraystring= br.readLine().split(" ");
DoublyLinkedList list= new DoublyLinkedList();
for(int i=0; i<arraystring.length; i++)
{
list.add(Integer.parseInt(arraystring[i]));
}
return list;
}
@Override
public String toString()
{
return head.toString();
}
}
This code truncates the first and the last element of the DLL (I have no idea why). Add a dummy first and last element and then it works fine.
public static final double LOG2= Math.log(2);
public static DoublyLinkedList.Node traverse(DoublyLinkedList.Node node, int offset)
{
DoublyLinkedList.Node temp= node;
if(offset>=0)
while(offset-->0)
temp= temp.next;
else
while(offset++<0)
temp=temp.prev;
return temp;
}
public static int getRootPos(int size)
{
int treeHeight= (int)(Math.ceil(Math.log(size)/LOG2));
return (int)(Math.pow(2,treeHeight)/2);
}
public static void buildTree(DoublyLinkedList.Node root, int size, int leftSize)
{
if(size<=1)
{
if(root!=null)
{
root.next= null;
root.prev= null;
}
return;
}
int leftLeftSize= getRootPos(leftSize);
DoublyLinkedList.Node leftSubtreeRoot=null;
if(leftLeftSize>0)
{
leftSubtreeRoot= traverse(root, leftLeftSize-leftSize);
buildTree(leftSubtreeRoot, leftSize, leftLeftSize);
}
int rightLeftSize= getRootPos(size-leftSize);
DoublyLinkedList.Node rightSubtreeRoot= null;
if(rightLeftSize>0)
{
rightSubtreeRoot= traverse(root, rightLeftSize);
buildTree(rightSubtreeRoot, size-leftSize, rightLeftSize);
}
root.prev= leftSubtreeRoot;
root.next= rightSubtreeRoot;
}
What you do not understand however, is the fact that right now we are given a matrix with a definite number of elements (Order(n) does not apply since n isn't variable). There are 676 of them to be precise. When you talk about finding the multiplication of each row and column, you are visiting each element twice. Therefore, number of calculations performed are equal to 676*2. Instead, if you take two arrays of size 26 each and store the cumulative result, you will have to visit every element only once. [See the code I posted below], thus reducing the number of calculations to 676.
I guess this problem is aimed to emphasize that sometimes the order doesn't matter, a heavy computation that takes seconds to complete should be used as less as possible. Obviously, a code with lesser computations would run considerably faster, even if its time complexity is equal to some other code (with more computations).
public static void resultHashedQuickPrintArraySum(int[] a, int[] b, int[] c)//O(n)<=n^2 . Efficient hashing.
{
boolean CON= c[c.length-1]-c[0]<a[a.length-1]+b[b.length-1]-a[0]-b[0];
int MINMAX= CON?c[c.length-1]-c[0]:a[a.length-1]+b[b.length-1]-a[0]-b[0];
int OFFSET= CON?c[0]:a[0]+b[0];
String[][] hashedArray= new String[(int)Math.ceil((double)(MINMAX-OFFSET)/(0x1<<8))][];
double alphaRatio= Math.ceil((double)(MINMAX-OFFSET)/(double)hashedArray.length);
for(int i=0; i<c.length; i++)//o(n)=n. O(n)<=n
{
int correctedNumber= c[i]-OFFSET;
int index= (int)((double)correctedNumber/alphaRatio);
if(index>=0&&index<hashedArray.length)
{
if(hashedArray[index]==null)
hashedArray[index]= new String[(int)Math.ceil(alphaRatio)];
int offsetIndex= correctedNumber-(int)((double)index*alphaRatio);
hashedArray[index][offsetIndex]=hashedArray[index][offsetIndex]==null?"":hashedArray[index][offsetIndex];
hashedArray[index][offsetIndex]+="k: "+i;
}
}
for(int i=0; i<a.length; i++)//o(n)=n^2. O(n)<=n^2
for(int j=0; j<b.length; j++)
{
int correctedNumber= a[i]+b[j]-OFFSET;
int index= (int)(((double)correctedNumber)/alphaRatio);
if(index>=0&&index<hashedArray.length&&hashedArray[index]!=null)
{
if(hashedArray[index][(correctedNumber-(int)((double)index*alphaRatio))]!=null)
System.out.println(hashedArray[index][(correctedNumber-(int)((double)index*alphaRatio))]+", i: "+i+", j: "+j);
}
}
}
public static int alternateBinarySearch(int[] array, int i)
{
int low1=0, high1= (int)Math.ceil(((double)array.length)/2)-1, mid1;
int low2=0, high2= array.length/2-1, mid2;
if(array[array.length-1]==i)
return array.length-1;
if(array[array.length-2]==i)
return array.length-2;
if(array[0]==i)
return 0;
if(array[1]==i)
return 1;
while(low1<high1-1||low2<high2-1)
{
mid1=(high1+low1)/2;
mid2=(high2+low2)/2;
if(array[2*mid1]==i)
return mid1*2;
else if(array[2*mid1]>i)
high1= mid1;
else
low1= mid1;
if(array[2*mid2+1]==i)
return mid2*2+1;
else if(array[2*mid2+1]>i)
high2= mid2;
else
low2= mid2;
}
return -1;
}
private static class Pair
{
int a, b;
public Pair(int a, int b)
{
this.a=a;
this.b= b;
}
public String toString()
{
return "i: "+a+", j: "+b;
}
}
public static void ultraQuickPrintArraySum(int[] a, int[] b, int[] c)//O(n)<=n^2 , Hashed. Get better hashing?
{
boolean CON= c[c.length-1]-c[0]<a[a.length-1]+b[b.length-1]-a[0]-b[0];
int LEN= CON?c[c.length-1]-c[0]:a[a.length-1]+b[b.length-1]-a[0]-b[0];
int OFFSET= CON?c[0]:a[0]+b[0];
ArrayList[] hashedArray= new ArrayList[LEN+1];
for(int i=0; i<a.length; i++)//o(n)=n^2. O(n)<=n^2
for(int j=0; j<b.length; j++)
if(a[i]+b[j]-c[0]>=0&&a[i]+b[j]-OFFSET<hashedArray.length)
{
if(hashedArray[a[i]+b[j]-OFFSET]==null)
hashedArray[a[i]+b[j]-OFFSET]= new ArrayList<Pair>();
hashedArray[a[i]+b[j]-OFFSET].add(new Pair(i, j));
}
for(int i=0; i<c.length; i++)//o(n)=n. O(n)<=n
if(c[i]-OFFSET<hashedArray.length&&hashedArray[c[i]-OFFSET]!=null)
System.out.println(hashedArray[c[i]-OFFSET]+", k: "+i);
}
public static void getFactorialPrimes(int N)
{
BigInteger factorial= new BigInteger("1");
BigInteger one= new BigInteger("1");
for(int i=0, nextNum=1; i<N;)
{
if(factorial.subtract(one).isProbablePrime(100))
{
System.out.println(factorial.subtract(one).toString());
i++;
}
if(factorial.add(one).isProbablePrime(100))
{
System.out.println(factorial.add(one).toString());
i++;
}
factorial= factorial.multiply(new BigInteger(""+(++nextNum)));
}
}
public static final int OR= 0x3ffffff;
public static boolean isValid(char[][] array, int pos, int[] orRow, int[] orCol)
{
if(pos==array.length-1)
return (orCol[pos]|array[pos][pos])==OR&&(orRow[pos]|array[pos][pos])==OR;
int cumRow= orCol[pos], cumCol= orRow[pos];
for(int i=pos; i<array.length; i++)
{
cumRow|=0x1<<((int)((int)array[pos][i]-(int)'a'));
cumCol|=0x1<<((int)((int)array[i][pos]-(int)'a'));
orRow[i]|=0x1<<((int)((int)array[pos][i]-(int)'a'));
orCol[i]|=0x1<<((int)((int)array[i][pos]-(int)'a'));
}
return (cumRow==OR&&cumCol==OR)?isValid(array, pos+1, orRow, orCol):false;
}
public static int getIndex(int[] array)
{
if(array.length==1)
return 0;
int sum= getSum(array);
int headSum= 0;
int tailSum= sum - array[0];
for(int i=1; i<array.length-1; i++)
{
headSum+= array[i-1];
tailSum-= array[i];
if(headSum==tailSum)
return i;
}
return -1;
}
ITERATIVE:
public static int[][] getMaximalCostMatrix(int[][] valueMatrix)
{
int[][] costMatrix= new int[valueMatrix.length][valueMatrix[0].length];
costMatrix[0][0]= valueMatrix[0][0];
for(int i=1; i<costMatrix.length; i++)
{
costMatrix[i][0]= valueMatrix[i][0] + costMatrix[i-1][0];
costMatrix[0][i]= valueMatrix[0][i] + costMatrix[0][i-1];
}
for(int i=1; i<costMatrix.length; i++)
{
costMatrix[i][i]= valueMatrix[i][i] + max(costMatrix[i-1][i], costMatrix[i][i-1]);
for(int j=i+1; j<costMatrix.length; j++)
{
costMatrix[i][j]= valueMatrix[i][j] + max(costMatrix[i-1][j], costMatrix[i][j-1]);
costMatrix[j][i]= valueMatrix[j][i]+ max(costMatrix[j-1][i], costMatrix[j][i-1]);
}
}
return costMatrix;
}
RECURSIVE
public static void getMaximalCostMatrix(int[][] valueMatrix, int[][] costMatrix, int i, int j)
{
if(i==0&&j==0)
costMatrix[i][j]= valueMatrix[i][j];
else
{
if(i-1>=0&&costMatrix[i-1][j]==0)
getMaximalCostMatrix(valueMatrix, costMatrix, i-1, j);
if(j-1>=0&&costMatrix[i][j-1]==0)
getMaximalCostMatrix(valueMatrix, costMatrix, i, j-1);
int p= i-1>=0?costMatrix[i-1][j]:0;
int q= j-1>=0?costMatrix[i][j-1]:0;
costMatrix[i][j]= valueMatrix[i][j] + max(p,q);
}
}
public static class BiNode
{
public BST.Node first, last;
}
public static BiNode convert(BST.Node root)
{
BiNode ret= new BiNode();
BiNode fl= new BiNode();
if(root.left!=null)
{
fl= convert(root.left);
fl.last.right= root;
root.left= fl.last;
}
ret.first= fl.first!=null?fl.first:root;
if(root.right!=null)
{
fl= convert(root.right);
fl.first.left= root;
root.right= fl.first;
}
ret.last= fl.last!=null?fl.last:root;
return ret;
}
public static void quadRotate(int[][] matrix, int i0, int j0, int i1, int j1, int i2, int j2, int i3, int j3)
{
matrix[i0][j0]+=matrix[i1][j1]+matrix[i2][j2]+matrix[i3][j3];
matrix[i1][j1]= matrix[i0][j0]- matrix[i1][j1]- matrix[i2][j2]- matrix[i3][j3];
matrix[i2][j2]= matrix[i0][j0]- matrix[i1][j1]- matrix[i2][j2]- matrix[i3][j3];
matrix[i3][j3]= matrix[i0][j0]- matrix[i1][j1]- matrix[i2][j2]- matrix[i3][j3];
matrix[i0][j0]= matrix[i0][j0]- matrix[i1][j1]- matrix[i2][j2]- matrix[i3][j3];
}
public static void rotate(int[][] matrix, int p0, int n)
{
if(n<=1)
{
return;
}
for(int i=0; i<n-1; i++)
{
quadRotate(matrix, p0, p0+i, p0+i, p0+n-1, p0+n-1, p0+n-1-i, p0+n-1-i, p0 );
}
rotate(matrix, p0+1, n-2);
}
public class LeastCommonAncestor {
private int[] tree;
public LeastCommonAncestor(int[] tree)
{
this.tree= new int[tree.length+1];
System.arraycopy(tree,0, this.tree, 1, tree.length);
}
public int getLCA(int a, int b)
{
int apos=-1, bpos=-1;
for(int i=0; (apos==-1||bpos==-1) && i<tree.length; i++)
{
apos= tree[i]==a?i:apos;
bpos= tree[i]==b?i:bpos;
}
if(apos*bpos<0)
return -1;
while(apos!=bpos)
{
if(apos>bpos)
apos/=2;
else bpos/=2;
}
return apos;
}
public static void main(String args[]) throws FileNotFoundException, IOException
{
BufferedReader br= new BufferedReader(new InputStreamReader( new FileInputStream(new File("C:\\LCA.txt"))));
System.out.println("Enter tree");
String[] treestring= br.readLine().split(" ");
int[] tree= new int[treestring.length];
for(int i=0; i<treestring.length; i++)
{
tree[i]= treestring[i].equals("NULL")?-1:Integer.parseInt(treestring[i]);
}
System.out.println("Enter A and B");
int a= Integer.parseInt(br.readLine());
int b= Integer.parseInt(br.readLine());
LeastCommonAncestor lca= new LeastCommonAncestor(tree);
int pos= lca.getLCA(a, b);
System.out.println(lca.tree[pos]);
}
}
public static LinkedList.Node findCircular(LinkedList.Node head)
{
HashSet<LinkedList.Node> hs= new HashSet<>();
LinkedList.Node tempNode= head, prevNode= null;
while(!hs.contains(tempNode))
{
hs.add(tempNode);
prevNode= tempNode;
tempNode= tempNode.next;
}
return prevNode;
}
I don't know why we are even talking about O(logN), if both the numbers are 4 byte integers, logN cannot be greater than 31. Working on that, here is the O(1) version of the algorithm. pow(a,b) where b is the power a has to be raised to. If b is taken to be s1s2u1u2s3...sN, where s indicates a set bit and u indicates an unset bit, then pow(a,b) will be equal to a^(2^s1)*a^(2^s2)*a^(2^s3)....a^(2^sN) where s1, s2..sN are the positions of the set bits of b.
The corresponding code (in java) is:
- nj September 04, 2012