loveCoding
BAN USERstatic void ListCombination(String str){
if(str != null && str.length()!=0)
RecCombine("",str);
}
static void RecCombine(String prefix,String rest){
if(rest.length() == 0)
System.out.print(prefix + " ");
else{
RecCombine(prefix + rest.charAt(0),rest.substring(1));
RecCombine(prefix,rest.substring(1));
}
}
1. Calculate number of Leafs (i.e. L) in preorder say it is nL
2. if nL =1, there is only one node i.e root
3. if nL>1 && nL is even , left and right subtree is of height nL/2
4. if nL>1 && nL is odd, one subtree is of height 1 and other is of height (nL-1)/2 (There are two trees possible in this case)
Once we have height of both subtrees we can construct trees.
@tallitester
We will terminate the loop if i>=k.
if i=k we know what it is.
if i>k, it means element at k was C.
static void printDivisors(int n){
System.out.println("1*" + n);
printDivisors("",1,n);
}
static void printDivisors(String prefix,int prev,int n){
if(n<2)
return;
int s = (int) Math.ceil(Math.sqrt(n));
for(int i = 2;i<=s;i++){
if(n%i == 0){
if(i>=prev && n/i>=i){
System.out.println(prefix + i + "*" + n/i);
printDivisors(prefix + i + "*",i,n/i);
}
}
}
}
If you are including 1 then 1*2*6 can also be one solution..
- loveCoding January 19, 2012If two linked list merge their last or first node has to be same..
So here is the algo O(m+n)
1 Compare the first nodes of both lists if equal return true else go to step 2.
2 Traverse first list to get the last node (NON NULL)
3. Traverse second to get the last node (NON NULL)
4. compare the two nodes, if equal then lists are merged.
Can you please elaborate the question with some examples?
- loveCoding January 18, 2012Wrong solution.
Case 2 is wrong when x>128 it can be B1 or B2
E.g. we have a (120)(129)(129) i.e. AB1B2 lets say k =2 i.e. B2
This is incorrect.. With this you can get a solution such that buyday > sellday which is NOT a valid solution
- loveCoding January 17, 2012This is incorrect.. With this you can get a solution such that buyday > sellday which is NOT a valid solution
- loveCoding January 17, 2012One way is to find this out in O(k)..
lets say A is one byte element and BC are two bytes i.e. B 1st byte and C is 2nd byte
1. Now start with i=0 i.e. first element
1a if element is b/w 0-127 it has to be A, increment i by one
1b if element is b/w 128-255 it has to be B, now increment i by 2 as next element has to be C , so i = i+2
repeat 1a and 1b until i>=k..
Make Hash of first array with noc(number off occurences) of each element..
Now go through second array if hash contains element and noc>0, add that element in intersection array.
Time O(n+m)
Space O(n)
First Add all nodes in a queue in inorder.
Now go through the queue and assign right/left pointers on adjacent elements.
O(n) time
Updated the code above please have a look, we can have one flag alrernate to manage that
- loveCoding January 12, 2012What is expected output for n=2..
I think in this case bd and db is same why do we need to print both...
so for abcd and n=2, number of combinations would be 6.
Please correct me if i am wrong..
Thanks..
You just need to do BFS... maintain a queue and print all childs.
In case of mirror image you need to make sure you put the right child in the queue first.
Code is below...
static void printTreebylevel(TreeNode root,boolean mirror){
if(root == null)
return;
LinkedList<TreeNode> list = new LinkedList<TreeNode>();
list.add(root);
while(list.isEmpty() == false){
int n = list.size();
String s = "";
boolean alternate = true;
while(n!=0){
TreeNode p = (TreeNode) list.remove();
n--;
s = s + p.data + " ";
if(mirror == false){
if(p.left!=null)
list.add(p.left);
if(p.right!=null)
list.add(p.right);
}else{
if(alternate==false){
if(p.right!=null)
list.add(p.right);
if(p.left!=null)
list.add(p.left);
}else{
if(p.right!=null)
list.add(p.right);
if(p.left!=null)
list.add(p.left);
}
alternate = !alternate;
}
}
System.out.println(s);
}
}
Have you really tried running my code.. is it to hard to run the code that is compilable.....run my code with any sample and let me know if it does not work...
Let me give you example for e.g I have an array {2,2,13,4,7,3,8,12,9,1,5}
Now I calculate sum array like
{2,4,17,21,28,31,39,52,60,61,66}
Now in this case my hashtable loop will not find any element that is double of any other element and hence it will next try
{2,13,4,7,3,8,12,9,1,5}
Now in this case sum array is
{2,15,19,26,29,37,49,58,59,64}
now in this case my hashtable will find 58 i.e. 2*29 and hence my it found one such subarray i.e starting at index 2(which in original array is index 1) and ending at 58(orinila array index 8.....
I hopw now you will get it.....
If NOT run my code and try with any sample.
In other words I dont have to go through all sub arrays
@Jeff, you mean hastable is O(n)???
- loveCoding January 11, 2012For length 10 findSubarray is called 21 times..
For n = 61, this number is 121
For n=100,this number is 199
Come on try the code yourself
For length 10 findSubarray is called 21 times..
For n = 61, this number is 121
For n=100,this number is 199
Come on try the code yourself
Below is the solution in Java
private static void printCombinationsforlength(String str, int n) {
printCombinationsforlength("",str,n);
}
public static void printCombinationsforlength(String prefix, String str, int n){
if(n == 1){
for(int i =0;i<str.length();i++)
System.out.print(prefix+str.charAt(i) + " ");
}
for(int i = 0;i<str.length();i++)
printCombinationsforlength(prefix+str.charAt(i),str.substring(i+1),n-1);
}
Oh Really... look at my code below and see the magic :-)
- loveCoding January 10, 2012In my step 2 I dont find all sub arrays, I will find only sub arrays containing either first element or last element.. so for 10 elements I will have 19 subarrays i.e. 2n-1
{1..10}{1..9}{1...8}.... 10 arrays
{2..10}{3..10}{4...10}.... 10 arrays
Ok Let me explain you in more detail. For e.g. lets take an array of four elements {a,b,c,d}---- Now my algorithm has two loops of O(n)... first loop starts from the first element and dropd next until reaches end i.e. it will find {a,b,c,d},{b,c,d},{c,d},{d} and second loop will drop element from end i.e. it will find {a,b,c},{a,b} and {a}.... So I have found all subarrays in O(2n) which is O(n)....
Notice here we are looking for contiguos subarrays NOT subsets so it is NOT O(n^2)....
Here is the code..For explanation see my comment above...
The method return Pair object i.e. {start-index,end-index}
static class Pair{
int start;
int end;
public Pair(int a,int b){
start = a;
end = b;
}
public boolean isGreaterthan(Pair p) {
int size = end-start;
if(size > (p.end - p.start))
return true;
return false;
}
public static Pair max(Pair p1, Pair p2, Pair p3) {
Pair max = null;
if(p1.end - p1.start > p2.end - p2.start)
max = p1;
else
max = p2;
if(p3.end - p3.start > max.end - max.start)
max = p3;
return max;
}
}
static Pair findSubArray(int[] a, int start, int end){
if(start>=end)
return new Pair(-1,-1);
//Calculate Sum Array
for(int i = start+1;i<=end;i++){
a[i] = a[i] + a[i-1];
}
int startindex = -1;
int endindex = -1;
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int j = start;j<end;j++){
map.put(2*a[j], j);
if(map.containsKey(a[j])){
int s = map.get(a[j]);
if( (j - start) > (endindex - startindex)){
endindex = j;
startindex = start;
}
}
}
Pair p1 = new Pair(startindex,endindex);
//reset
for(int i = end;i>start;i--){
a[i] = a[i] - a[i-1];
}
Pair p2 = new Pair(-1,-1);
Pair p3 = new Pair(-1,-1);
if(end==a.length-1)
p2 = findSubArray(a,start+1,end);
if(start==0)
p3 = findSubArray(a,start,end-1);
return Pair.max(p1,p2,p3);
}
Lets break the problem
1) If the array has an index j such that sum(0 to j) = sum(k-j to k) , we can identify this in O(n) ->
a) Calculate sum array i.e. for { 4,7,3,8,12,9,1} Sum Array will be {4,11,14,22,34,43,44}
b) Now go through loop once again and build hasmap of 2*thatelement, if we already have 2*that element in hash map, means we have found such an array store the start-index and end-index.
2) Now we have to find sub arrays , we can do that in O(n) too
a) first start full array i.e. 0 to length-1 then 1 to length -1 -> 2 - length-1 ... n times
b) start dropping element from end i.e. 0 to length -1 -> o - length -2 ... n times
Now step 2 is O(n) and at every step we will perform step 1 which is also 0(n), so the overall complexity is O(n^2)
Will post the code soon
static void printTreebylevel(TreeNode root){
if(root == null)
return;
LinkedList<TreeNode> list = new LinkedList<TreeNode>();
list.add(root);
while(list.isEmpty() == false){
int n = list.size();
String s = "";
while(n!=0){
TreeNode p = (TreeNode) list.remove();
n--;
s = s + p.data + " ";
if(p.left!=null)
list.add(p.left);
if(p.right!=null)
list.add(p.right);
}
System.out.println(s);
}
}
Looks like somebody changed the question itself... :)
My solution is for different question
public static int LSBFibbonacci(int n){
if(n <= 1)
return n;
int a1 = 1;
int a2 = 1;
int res = 1;
for(int i=3;i<=n;i++){
res = (a1 + a2)%1000000;
a1 = a2 % 1000000;
a2 = res % 1000000;
}
return res;
}
It can be solved by simple DP
static int minCutsforPalindrome(String str){
if(str == null)
return -1;
if(str.length()<2)
return str.length();
int[] min = new int[str.length()+1];
min[0] = 0;
min[1] = 1;
for(int i =2;i<=str.length();i++){
min[i] = min[i-1] + 1;
int p = hasPalindrome(str,i-1);
if(p!=-1){
min[i] = Math.min(min[i], 1+min[p]);
}
}
return min[str.length()]-1;
}
private static int hasPalindrome(String str, int index) {
for(int i=0;i<index;i++){
if(isPalindrome(str.substring(i,index+1)))
return i;
}
return -1;
}
private static boolean isPalindrome(String str) {
if(str.length()<=1)
return true;
int i =0;
int j = str.length() - 1;
while(i<j){
if(str.charAt(i) == str.charAt(j)){
i++;
j--;
}else{
return false;
}
}
return true;
}
Full code using DP is below, it also prints out the steps :)
public static int[][] minSteps(int[] a, int target){
int[] min = new int[target+1];
int[][] soln = new int[target+1][3];
soln[0] = new int[]{0,0,0};
for(int i =1;i<=target;i++){
soln[i][0] = i;
soln[i][1] = i;
soln[i][2] = 0;
}
min[0] = 0;
min[1] = 1;
for(int i =2;i<=target;i++){
min[i] = min[i-1]+1;
soln[i][0] = 1;
soln[i][1] = 1;
soln[i][2] = i-1;
for(int p=0;p<a.length;p++){
if(a[p]==1 || i<a[p])
continue;
int res = i/a[p] + min[i%a[p]];
if(res<min[i]){
soln[i][0] = i/a[p];
soln[i][1] = a[p];
soln[i][2] = i%a[p];
min[i] = res;
}
}
}
return soln;
}
private static void printSolution(int[][] solution,int target) {
int steps = solution[target][0];
String details = "" + solution[target][0] + " X " + solution[target][1];
int j = solution[target][2];
while(j!=0){
steps += solution[j][0];
details += " -> " + solution[j][0] + " X " + solution[j][1];
j = solution[j][2];
}
System.out.println("The number of min steps are " + steps);
System.out.println("Detailed steps are " + details);
}
You do not need to do two traversals.
- loveCoding December 29, 2011Assuming we can destroy array M and gaps are represented by ' '.
below is the code
void merge(char[] a, char[] b){
int j = 0;
for(int i= 0;i<a.length;i++){
if(j>=b.length)
break;//Array is Sorted
if(a[i]==' '){
if(i==a.length() || a[i+1]>b[j]){
swap(a[i],b[j])
j++;
}else{
swap(a[i],a[i+1])
}
}else{
if(b[j]<a[i])
swap(b[j],a[i]);
}
}
The logic is here.
For example we have "abc", Now parse through string character by character.
For a :- make "a" the root, call "MakeBTs(bc") for right subtrees, which will produce two tree combination., SO for a we will have two BTs
For b: make "b" the parent,now call MakeBTs("a" for left subtrees and call MakeBTs("b") for right sub trees, this will produce 1 BT.
Similarily for c we will have 2 BTs.
Hope its clear now.
first calculate int n = floor[log(N/C + 1)/log2]
Now all levels less then n will have C amount of water and glasses at level n will have
(N-(2^n-1)C)/2^n.
lets take an example suppose we have N = 4C
in this case n = 2, which means glasses at level 0 and 1(i.e < 2) will have C amount of water and glass at level 2 will have (N-3C)/4 i.e C/4 each.
Sorry guys Here is the solution for making Trees
static ArrayList<TreeNode> MakeBTs(String str){
if(str.length() == 0)
return null;
ArrayList<TreeNode> btlist = new ArrayList<TreeNode>();
if(str.length() == 1){
btlist.add(new TreeNode(str.charAt(0)));
return btlist;
}
if(str.length() == 2){
TreeNode p = new TreeNode(str.charAt(0));
p.right = new TreeNode(str.charAt(1));
btlist.add(p);
TreeNode q = new TreeNode(str.charAt(1));
q.left = new TreeNode(str.charAt(0));
btlist.add(q);
return btlist;
}
for(int i=0;i<str.length();i++){
ArrayList<TreeNode> left = MakeBTs(str.substring(0,i));
ArrayList<TreeNode> right = MakeBTs(str.substring(i+1));
if(left==null && right==null){
btlist.add(new TreeNode(str.charAt(i)));
}else if(left!=null && right!=null){
for(TreeNode l:left){
TreeNode p = new TreeNode(str.charAt(i));
p.left = l;
for(TreeNode r:right){
p.right = r;
btlist.add(p);
}
}
}else{
if (right != null) {
for (TreeNode r : right) {
TreeNode p = new TreeNode(str.charAt(i));
p.right = r;
btlist.add(p);
}
}else if(left!=null){
for (TreeNode l : left) {
TreeNode p = new TreeNode(str.charAt(i));
p.left = l;
btlist.add(p);
}
}
}
}
return btlist;
}
We can store the digits in reverse order.
That is for 9 power tree it will return 9 -> 2 -> 7
Below is the code
public static Node power(int num,int pow){
if(pow<0)
return null;
if(pow == 0)
return new Node(1);
Node q = new Node(num);
pow--;
while(pow!=0){
Multiply(q,num);
pow--;
}
return q;
}
public static void Multiply(Node head, int n){
if(head==null)
return;
Node q = head;
int carry = 0;
while(q!=null){
int res = q.data*n + carry;
if(res<10){
q.data = res;
carry = 0;
}else{
q.data = res %10;
carry = res/10;
}
q = q.next;
}
if(carry!=0){
append(head,carry);
}
}
Man what about if faster car is following slower car..... There will be accidents :)
- loveCoding December 28, 2011public static void printPowers(){
int no = 1;
PriorityQueue a = new PriorityQueue();
System.out.print(no + " ");
while(no<100){
if(a.contains(no*2) == false)
a.add(no*2);
if(a.contains(no*5) == false)
a.add(no*5);
no = (Integer) a.remove();
System.out.print(no + " ");
}
}
I thinks its wrong, we need to make sure strings are concatenated in correct order.
For e.g. if we are given stringlengths like 1-5- 2-3-4, we cannot combine 1 and 2 although we can combine 1and 5 or 5and 2
Please give a code if you think it can be done without O(n) space
- loveCoding December 27, 2011yes this need not be BST.... it can be any tree....
- loveCoding December 27, 2011Considering tree has got negative values else otherwise max will be the tree itself.
Define one HashMap<TreeNode,Integer> to store sum of node.This is to make sure we dont calculate the sum of one subtree more than once.
static int SumNode(TreeNode node){
int sum = 0;
if(node == null)
return 0;
else{
if(map.containsKey(node))
return map.get(node);
else{
sum = node.data + SumNode(node.left) + SumNode(node.right);
map.put(node,sum);
return sum;
}
}
}
static int MaxSum(TreeNode root){
if(root == null)
return 0;
else
return Math.max(SumNode(root),Math.max(MaxSum(root.left),MaxSum(root.right)));
}
One solution can be like that.
Initialize max = -1,imax =-1,jmax = -1
First compare the first element with all elements find the largest j for which a{j] > a[0]. max = j,,imax = i,jmax = j;
Now in second step compare the last element with all previous elements find the largest j for which a{length-1] > a[i]. max = lengh -1 -j,imax = i,jmax = j;
We need to repeat above steps until max != -1 i.e we have found max and that is going to be our result.
I am passing min and max value for every node... for eg if i go to left node, i will pass current node's value as a max for next node and so on.
- loveCoding December 23, 2011First check at every node(we can do in order traversal) if the patterns exist.
If we find a pattern at any given node, we add that in array list
Lets define a new class
pair {
Node startnode
Node endnode
int length;}
Now when you find a pattern at a node say startnode to endnode.
Now adding part
if array list already have this startnode as any of the pair's endnode, increment the lenth of that pair by 1 and replace the endnode with new endnode.
else just add this new pair in array list
once done traverse the array list to find the max length.
this will be O(n+2m) n is no of nodes and m is number of sequences
so this is O(n)
what is that? please explain your question in more details if possible
- loveCoding December 23, 2011static boolean isBST(TreeNode root){
return isBST(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
}
static boolean isBST(TreeNode root,int min,int max){
if(root == null)
return true;
if(root.data<min || root.data>max)
return false;
if(root.left!=null && root.left.data > root.data ||
root.right!=null && root.right.data < root.data)
return false;
return(isBST(root.left,min,root.data) && isBST(root.right,root.data,max));
}
Thanks....
Here is the new one
static boolean isBST(TreeNode root){
return isBST(root,Integer.MIN_VALUE,Integer.MAX_VALUE);
}
static boolean isBST(TreeNode root,int min,int max){
if(root == null)
return true;
if(root.data<min || root.data>max)
return false;
if(root.left!=null && root.left.data > root.data ||
root.right!=null && root.right.data < root.data)
return false;
return(isBST(root.left) && isBST(root.right));
}
- loveCoding January 25, 2012