[algogeeks] confusion
#includestdio.h int main() { int i=1; printf(%d\n,printf(%d,printf(%d,i))); return 0; } output is 111..i was expecting it to be 11..plz explain?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] confusion
printf(%d\n,printf(%d,printf(%d,i))); - 1 -- This will print 1 and printf returns 1 2 -- This will print the return value of printf 1 and it will return 1. --- 3 --- This will print the return value of printf 2 and it will again return 1 but there is no printf to print it. Hope I make it clear to you. -Shafi On Thu, Jul 29, 2010 at 2:16 PM, tarak mehta tarakmeht...@gmail.com wrote: #includestdio.h int main() { int i=1; printf(%d\n,printf(%d,printf(%d,i))); return 0; } output is 111..i was expecting it to be 11..plz explain?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] ALGORITHM
Good approach Shiv.I think thats the best way to do so.The question does not strictly say we have consecutive n-1 distinct numbers.So,its not worth considering that particular case. On Thu, Jul 29, 2010 at 12:08 AM, Shiv ... shivsinha2...@gmail.com wrote: What if the number are not consecutive? My approach- Put the numbers in a hash till a collision occurs. On Wed, Jul 28, 2010 at 9:21 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: Solution : 1. Find Xor of numbers from 1 to n-1. 2. Find Xor of the numbers present in the array. 3. Xor the results from step 1 and 2 you will get the repeated number. On Wed, Jul 28, 2010 at 8:46 PM, akshay akshayrastogi2...@gmail.comwrote: An array of unsorted numbers n is given with one no.repeated once ie n-1 distinct nos to find duplicate no. in o(n) complexity -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Ashish -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Oracle-Java Developer interview question
Width of a Tree = maximum number of nodes at the same level. Example: a bc d e f g h i j Here, the max. width is 4 at level 3-d, e, f, g Algo to find width: 1. Push node on stack1 2. Pop node from stack1 if not empty 3. visit node and push children on stack2 4. goto 2 if stack1 not empty 5. if stack1 empty, number of elements in stack 2width then width= number of elements on stack2 6. repeat steps 2-5 for stack2 basically keep pushing children on stack until 1 stack is not empty, the value when it is empty will give the width at that level. Use one variable to store this width by checking if current width is greater. -Minotauraus. On Jul 26, 5:23 am, umesh kewat umesh1...@gmail.com wrote: use levelorder traversal and calculate the number of node in same level by putting some condition :) On Mon, Jul 26, 2010 at 1:53 PM, vineel yalamarth vineelyalamar...@gmail.com wrote: No dude, they asked me to find width , in the sense ... find the maximum number of nodes in any level. And if you know how to find the diameter do post it -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Umesh kewat- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: finding repeated substrings
I'd say use a hash table to store node/pointer for quick lookup instead. For each node in the tree query the hash table. If there is a collision (value exists) get point to that node from the table and traverse the subtree, until you reach leaf nodes or find that the subtrees are not the same. For large trees you'll end up traversing them to convert it to a prefix notation and then probably spend (worst case) O(n^2) time in finding matches. To make comparisons faster you could store number of immediate child nodes for comparison. If number is not the same, subtrees aren't, move on. -Minotauruas. On Jul 27, 9:02 am, Harsha Nagesh harshasnag...@gmail.com wrote: Hi, Given a string, I am interested in finding all repeated substrings of any length (not just the longest substring). Can anybody point me to the right algorithm/literature for this problem? My original problem is finding repeated subtrees in a tree that has nodes of different kind. My plan is to convert the tree into a prefix notation and solve the above mentioned substring problem. Thanks Harsha -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: ALGORITHM
If numbers are consecutive you can do better. Calculate (n-1)(n-2)/2 - sum of all elements in the array. That'll require one less loop compared to XORing twice. -Minotauraus. On Jul 28, 8:51 am, Apoorve Mohan apoorvemo...@gmail.com wrote: Solution : 1. Find Xor of numbers from 1 to n-1. 2. Find Xor of the numbers present in the array. 3. Xor the results from step 1 and 2 you will get the repeated number. On Wed, Jul 28, 2010 at 8:46 PM, akshay akshayrastogi2...@gmail.com wrote: An array of unsorted numbers n is given with one no.repeated once ie n-1 distinct nos to find duplicate no. in o(n) complexity -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: ALGORITHM
@Shiv Collision is itself a wel known issue in hashing and much need to be done to avoid collision. When you say your appraoch is hash the numbers, how do u make sure without knowing the nature of the numbers that you can hash them without bringing ing collision of inequal items of the array? On Jul 28, 11:38 pm, Shiv ... shivsinha2...@gmail.com wrote: What if the number are not consecutive? My approach- Put the numbers in a hash till a collision occurs. On Wed, Jul 28, 2010 at 9:21 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: Solution : 1. Find Xor of numbers from 1 to n-1. 2. Find Xor of the numbers present in the array. 3. Xor the results from step 1 and 2 you will get the repeated number. On Wed, Jul 28, 2010 at 8:46 PM, akshay akshayrastogi2...@gmail.comwrote: An array of unsorted numbers n is given with one no.repeated once ie n-1 distinct nos to find duplicate no. in o(n) complexity -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] confusion
every printf statement wll return how many number of parameter/variable print r printed so 2nd nested wll print number 1 n remaing two printf statement wll print number of parameters are printed so total three 1's .:) -- Prashant Kulkarni || Lokaha Samastaha Sukhino Bhavanthu || || Sarve Jana Sukhino Bhavanthu || On Thu, Jul 29, 2010 at 2:16 PM, tarak mehta tarakmeht...@gmail.com wrote: #includestdio.h int main() { int i=1; printf(%d\n,printf(%d,printf(%d,i))); return 0; } output is 111..i was expecting it to be 11..plz explain?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] confusion
Hi tarak, output is right, because every printf print 1 so there is 3 printf call...so 111 is right On Thu, Jul 29, 2010 at 2:16 PM, tarak mehta tarakmeht...@gmail.com wrote: #includestdio.h int main() { int i=1; printf(%d\n,printf(%d,printf(%d,i))); return 0; } output is 111..i was expecting it to be 11..plz explain?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Umesh kewat -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] confusion
printf returns the number of character it prints so output is ok it is 111 see this o/p you will understand #includestdio.hint main(){int i=1;printf(%d\n,printf(%d\n,printf(%d,i))); return 0;} http://codepad.org/gLGMDdoU -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] confusion
printf(%d\n,printf(%d\n,printf(%d,i))); return 0; 12--3 remove the new line '\n' character from 2nd printf it will print 111 because printf function returns number of character displayed. New line is considered as one chracter. In original questions 2nd printf does not have \n chracter. -Shafi On Thu, Jul 29, 2010 at 2:29 PM, harit agarwal agarwalha...@gmail.comwrote: printf returns the number of character it prints so output is ok it is 111 see this o/p you will understand #includestdio.hint main(){int i=1; printf(%d\n,printf(%d\n,printf(%d,i))); return 0;} http://codepad.org/gLGMDdoU -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Shafi Ahmad The difficult we do immediately, the impossible takes a little longerUS Army -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: ALGORITHM
I think we can assume a perfect hashing to exist. [Please correct me if I am wrong] Implementing one, is a different issue. :)) Other than hashing, we can use BST or Heap. ~ O(klog(n)) On Thu, Jul 29, 2010 at 1:07 PM, sourav souravs...@gmail.com wrote: @Shiv Collision is itself a wel known issue in hashing and much need to be done to avoid collision. When you say your appraoch is hash the numbers, how do u make sure without knowing the nature of the numbers that you can hash them without bringing ing collision of inequal items of the array? On Jul 28, 11:38 pm, Shiv ... shivsinha2...@gmail.com wrote: What if the number are not consecutive? My approach- Put the numbers in a hash till a collision occurs. On Wed, Jul 28, 2010 at 9:21 PM, Apoorve Mohan apoorvemo...@gmail.com wrote: Solution : 1. Find Xor of numbers from 1 to n-1. 2. Find Xor of the numbers present in the array. 3. Xor the results from step 1 and 2 you will get the repeated number. On Wed, Jul 28, 2010 at 8:46 PM, akshay akshayrastogi2...@gmail.com wrote: An array of unsorted numbers n is given with one no.repeated once ie n-1 distinct nos to find duplicate no. in o(n) complexity -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: ALGORITHM
#includestdio.h int main() { int a[] = { 10,5,6,8,1,10,8,7,9,9}; /* Assuming a[i] is in {i=1,N} */ int N = 10,index,j; int i; for (i = 0; i N; i++) { index = a[i] % N; if (a[index] N) { printf(Duplicate number is %d\n,a[i]%N); // break; } a[index] += N; } //restore the array for (j = 0; j i; j++){ if (a[j] N a[j]%10 != 0){ a[j] %= N; }else if(a[j] N a[j]%10 == 0){ a[j] = N; } printf(%d ,a[j]); } printf(\n); return 1; } On Thu, Jul 29, 2010 at 7:46 PM, Shiv ... shivsinha2...@gmail.com wrote: I think we can assume a perfect hashing to exist. [Please correct me if I am wrong] Implementing one, is a different issue. :)) Other than hashing, we can use BST or Heap. ~ O(klog(n)) On Thu, Jul 29, 2010 at 1:07 PM, sourav souravs...@gmail.com wrote: @Shiv Collision is itself a wel known issue in hashing and much need to be done to avoid collision. When you say your appraoch is hash the numbers, how do u make sure without knowing the nature of the numbers that you can hash them without bringing ing collision of inequal items of the array? On Jul 28, 11:38 pm, Shiv ... shivsinha2...@gmail.com wrote: What if the number are not consecutive? My approach- Put the numbers in a hash till a collision occurs. On Wed, Jul 28, 2010 at 9:21 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: Solution : 1. Find Xor of numbers from 1 to n-1. 2. Find Xor of the numbers present in the array. 3. Xor the results from step 1 and 2 you will get the repeated number. On Wed, Jul 28, 2010 at 8:46 PM, akshay akshayrastogi2...@gmail.comwrote: An array of unsorted numbers n is given with one no.repeated once ie n-1 distinct nos to find duplicate no. in o(n) complexity -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Shafi Ahmad The difficult we do immediately, the impossible takes a little longerUS Army -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Oracle-Java Developer interview question
@Minotauraus I feel Queue gives more picture. Thanks, Sathaiah Dontula On Thu, Jul 29, 2010 at 3:53 AM, Minotauraus anike...@gmail.com wrote: Width of a Tree = maximum number of nodes at the same level. Example: a bc d e f g h i j Here, the max. width is 4 at level 3-d, e, f, g Algo to find width: 1. Push node on stack1 2. Pop node from stack1 if not empty 3. visit node and push children on stack2 4. goto 2 if stack1 not empty 5. if stack1 empty, number of elements in stack 2width then width= number of elements on stack2 6. repeat steps 2-5 for stack2 basically keep pushing children on stack until 1 stack is not empty, the value when it is empty will give the width at that level. Use one variable to store this width by checking if current width is greater. -Minotauraus. On Jul 26, 5:23 am, umesh kewat umesh1...@gmail.com wrote: use levelorder traversal and calculate the number of node in same level by putting some condition :) On Mon, Jul 26, 2010 at 1:53 PM, vineel yalamarth vineelyalamar...@gmail.com wrote: No dude, they asked me to find width , in the sense ... find the maximum number of nodes in any level. And if you know how to find the diameter do post it -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Umesh kewat- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: ALGORITHM
@above: but this may lead to overflow of the integer as you don't know what is n. if the value of n is large then you can;t do this On Thu, Jul 29, 2010 at 3:26 AM, Minotauraus anike...@gmail.com wrote: If numbers are consecutive you can do better. Calculate (n-1)(n-2)/2 - sum of all elements in the array. That'll require one less loop compared to XORing twice. -Minotauraus. On Jul 28, 8:51 am, Apoorve Mohan apoorvemo...@gmail.com wrote: Solution : 1. Find Xor of numbers from 1 to n-1. 2. Find Xor of the numbers present in the array. 3. Xor the results from step 1 and 2 you will get the repeated number. On Wed, Jul 28, 2010 at 8:46 PM, akshay akshayrastogi2...@gmail.com wrote: An array of unsorted numbers n is given with one no.repeated once ie n-1 distinct nos to find duplicate no. in o(n) complexity -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Oracle-Java Developer interview question
do the level order traversal of the binary tree and keep the count of the stack...thats the width of the tree.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] recursive
void levelordertraversal(struct node* root,height) { int i=0; for(i=1;i=height(root);i++ printlevel(root,i); } void printlevel(struct node *root, level) { if(root == null) return; else if(level==1) printf(%d,root-data); else if(level1) { printlevel(root-left,level-1); printlevel(root-right,level-1); } } -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Amazon Placement Question
I attended Amazon placement test today . There was a question where i got confused.It is as follows. Give an algorithm to connect all nodes in one level of a binary tree . 5 5 / \ / \ 8 2 8 2 / \ / / \ / 1 2 61 --- 2 --6 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
On Thu, Jul 29, 2010 at 11:35 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: please explain q ..i didnt understand On Thu, Jul 29, 2010 at 11:01 AM, irfan irfannase...@gmail.com wrote: I attended Amazon placement test today . There was a question where i got confused.It is as follows. Give an algorithm to connect all nodes in one level of a binary tree . 5 5 / \ / \ 8 2 8 2 / \ / / \ / 1 2 61 --- 2 --6 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Sorry for that. I attached a jpg file showing what shud the algo do . Question is that, we are given a tree. algo shud connect all the nodes which are in same level. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. attachment: tree.jpg
Re: [algogeeks] Amazon Placement Question
solution is straight forward identifying nodes at different levels and making connection between them using a FLAG node On Thu, Jul 29, 2010 at 11:26 AM, irfan naseef irfannase...@gmail.comwrote: On Thu, Jul 29, 2010 at 11:35 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: please explain q ..i didnt understand On Thu, Jul 29, 2010 at 11:01 AM, irfan irfannase...@gmail.com wrote: I attended Amazon placement test today . There was a question where i got confused.It is as follows. Give an algorithm to connect all nodes in one level of a binary tree . 5 5 / \ / \ 8 2 8 2 / \ / / \ / 1 2 61 --- 2 --6 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Sorry for that. I attached a jpg file showing what shud the algo do . Question is that, we are given a tree. algo shud connect all the nodes which are in same level. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
I think use bfs ... On Thu, Jul 29, 2010 at 11:26 AM, irfan naseef irfannase...@gmail.comwrote: On Thu, Jul 29, 2010 at 11:35 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: please explain q ..i didnt understand On Thu, Jul 29, 2010 at 11:01 AM, irfan irfannase...@gmail.com wrote: I attended Amazon placement test today . There was a question where i got confused.It is as follows. Give an algorithm to connect all nodes in one level of a binary tree . 5 5 / \ / \ 8 2 8 2 / \ / / \ / 1 2 61 --- 2 --6 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Sorry for that. I attached a jpg file showing what shud the algo do . Question is that, we are given a tree. algo shud connect all the nodes which are in same level. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding repeated substrings
hi Minotauruas, For each node in the tree query the hash table. If there is a collision (value exists) get point to that node from the table and traverse the subtree, until you reach leaf nodes or find that the subtrees are not the same. can you explain this above statement in an bit more clearer way.. TIA On Thu, Jul 29, 2010 at 3:37 AM, Minotauraus anike...@gmail.com wrote: I'd say use a hash table to store node/pointer for quick lookup instead. For each node in the tree query the hash table. If there is a collision (value exists) get point to that node from the table and traverse the subtree, until you reach leaf nodes or find that the subtrees are not the same. For large trees you'll end up traversing them to convert it to a prefix notation and then probably spend (worst case) O(n^2) time in finding matches. To make comparisons faster you could store number of immediate child nodes for comparison. If number is not the same, subtrees aren't, move on. -Minotauruas. On Jul 27, 9:02 am, Harsha Nagesh harshasnag...@gmail.com wrote: Hi, Given a string, I am interested in finding all repeated substrings of any length (not just the longest substring). Can anybody point me to the right algorithm/literature for this problem? My original problem is finding repeated subtrees in a tree that has nodes of different kind. My plan is to convert the tree into a prefix notation and solve the above mentioned substring problem. Thanks Harsha -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Sony -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: finding repeated substrings
Use suffix trie. On 30 July 2010 00:50, Sony Jose sonyj...@gmail.com wrote: hi Minotauruas, For each node in the tree query the hash table. If there is a collision (value exists) get point to that node from the table and traverse the subtree, until you reach leaf nodes or find that the subtrees are not the same. can you explain this above statement in an bit more clearer way.. TIA On Thu, Jul 29, 2010 at 3:37 AM, Minotauraus anike...@gmail.com wrote: I'd say use a hash table to store node/pointer for quick lookup instead. For each node in the tree query the hash table. If there is a collision (value exists) get point to that node from the table and traverse the subtree, until you reach leaf nodes or find that the subtrees are not the same. For large trees you'll end up traversing them to convert it to a prefix notation and then probably spend (worst case) O(n^2) time in finding matches. To make comparisons faster you could store number of immediate child nodes for comparison. If number is not the same, subtrees aren't, move on. -Minotauruas. On Jul 27, 9:02 am, Harsha Nagesh harshasnag...@gmail.com wrote: Hi, Given a string, I am interested in finding all repeated substrings of any length (not just the longest substring). Can anybody point me to the right algorithm/literature for this problem? My original problem is finding repeated subtrees in a tree that has nodes of different kind. My plan is to convert the tree into a prefix notation and solve the above mentioned substring problem. Thanks Harsha -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Sony -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, soumya prasad ukil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Oracle-Java Developer interview question
Yeah, you can do it either way. You can even add a dummy element instead of checking for empty and popping each time. But basically yeah, that's how I'd do it. Manjunath put it in a nice concise way. On Jul 29, 3:42 am, Sathaiah Dontula don.sat...@gmail.com wrote: @Minotauraus I feel Queue gives more picture. Thanks, Sathaiah Dontula On Thu, Jul 29, 2010 at 3:53 AM, Minotauraus anike...@gmail.com wrote: Width of a Tree = maximum number of nodes at the same level. Example: a b c d e f g h i j Here, the max. width is 4 at level 3-d, e, f, g Algo to find width: 1. Push node on stack1 2. Pop node from stack1 if not empty 3. visit node and push children on stack2 4. goto 2 if stack1 not empty 5. if stack1 empty, number of elements in stack 2width then width= number of elements on stack2 6. repeat steps 2-5 for stack2 basically keep pushing children on stack until 1 stack is not empty, the value when it is empty will give the width at that level. Use one variable to store this width by checking if current width is greater. -Minotauraus. On Jul 26, 5:23 am, umesh kewat umesh1...@gmail.com wrote: use levelorder traversal and calculate the number of node in same level by putting some condition :) On Mon, Jul 26, 2010 at 1:53 PM, vineel yalamarth vineelyalamar...@gmail.com wrote: No dude, they asked me to find width , in the sense ... find the maximum number of nodes in any level. And if you know how to find the diameter do post it -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Umesh kewat- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
are the nodes having an extra pointer for sibling?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] number of BST's
Given the numbers from 1 to n, write an algorithm to find how many distinct binary search trees can be formed.. eg n=4, no of distinct bst's are 14. ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
BFS On Thu, Jul 29, 2010 at 11:56 PM, irfan naseef irfannase...@gmail.comwrote: On Thu, Jul 29, 2010 at 11:35 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: please explain q ..i didnt understand On Thu, Jul 29, 2010 at 11:01 AM, irfan irfannase...@gmail.com wrote: I attended Amazon placement test today . There was a question where i got confused.It is as follows. Give an algorithm to connect all nodes in one level of a binary tree . 5 5 / \ / \ 8 2 8 2 / \ / / \ / 1 2 61 --- 2 --6 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Sorry for that. I attached a jpg file showing what shud the algo do . Question is that, we are given a tree. algo shud connect all the nodes which are in same level. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Generate a number
An algorithm to print all the 10-digit nos such that first 1 digit is divisible by 1, first 2 digits by 2, first 3 digits by 3 and so on...first 9 digits by 9. I think the tenth digit can be anything from 0 to 9. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
Use a recursive functionthis below function will add up all nodes at the same level. void Traverse(Node n,int level, LinkedList list){ if(n==null) return; if(nlist.size()) list.add(n.value); else list.set(list.get(level)+n.value); Traverse(n.left,level+1,list); Traverse(n.right,level+1,list); } On Fri, Jul 30, 2010 at 12:03 AM, ashish agarwal ashish.cooldude...@gmail.com wrote: I think use bfs ... On Thu, Jul 29, 2010 at 11:26 AM, irfan naseef irfannase...@gmail.comwrote: On Thu, Jul 29, 2010 at 11:35 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: please explain q ..i didnt understand On Thu, Jul 29, 2010 at 11:01 AM, irfan irfannase...@gmail.com wrote: I attended Amazon placement test today . There was a question where i got confused.It is as follows. Give an algorithm to connect all nodes in one level of a binary tree . 5 5 / \ / \ 8 2 8 2 / \ / / \ / 1 2 61 --- 2 --6 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Sorry for that. I attached a jpg file showing what shud the algo do . Question is that, we are given a tree. algo shud connect all the nodes which are in same level. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
Algo: 1. find height of tree 2. do level order traversal i at each level store the address of each tree node in the data part of a linked node and form linked list of the nodes ii store the header of a linked list at a certain level in an array 3. return array.// gives final structure complexity - T(n) =O(n) S(n)=O(h+n ) //h=height of tree //CODE //tree structure struct node { int data; struct node * left, *right}; // linked list structure struct linkNode{ struct node * data; struct linkNode * next; } struct linkNode** func(struct node * root){ struct linkNode ** array; int i, h=height(root); for(i=1;i=h;i++) array[i-1]=levelOrderTraversal(root, i); return array;// final tree structure } //max height of tree int height(struct node *root){ int hL=height(root-left); int hR=height(root-right); return 1+ HRHL?HR:HL; } struct nodelink* levelOrderTraversal(struct node*root, int level){ if(root==NULL) return NULL; if (level==1) return createLinkNode(root); // create a node of a singly l struct LinkNode *ptr; if(level1){ ptr=levelOrderTraversal(root-left,level-1); ptr-next=levelOrderTraversal(root-right,level-1); } return ptr; } struct linkNode * createLinkNode(struct node * root){ struct linkNode* newNode=(struct linkNode*) malloc(sizeof(struct linkNode)); newNode-data=root; newNode-next=NULL; } -- Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Amazon Placement Question
Yeah use BFS, push the nodes on a stack and make them point to each other. How they point depends on the question, which needs clarification. Should they ALL be connected to each other as in A to B and A to C and B to C or just A to B and B to C. Either way, the above approach should work fine. -Minotauraus On Thu, Jul 29, 2010 at 11:35 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: please explain q ..i didnt understand On Thu, Jul 29, 2010 at 11:01 AM, irfan irfannase...@gmail.com wrote: I attended Amazon placement test today . There was a question where i got confused.It is as follows. Give an algorithm to connect all nodes in one level of a binary tree . 5 5 / \ / \ 8 2 8 2 / \ / / \ / 1 2 6 1 --- 2 --6 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Sorry for that. I attached a jpg file showing what shud the algo do . Question is that, we are given a tree. algo shud connect all the nodes which are in same level. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
@ srikant , trhe structure of binary tree have to be modified for this solution right..as nodes may have 3 links On Fri, Jul 30, 2010 at 12:03 AM, ashish agarwal ashish.cooldude...@gmail.com wrote: I think use bfs ... On Thu, Jul 29, 2010 at 11:26 AM, irfan naseef irfannase...@gmail.comwrote: On Thu, Jul 29, 2010 at 11:35 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: please explain q ..i didnt understand On Thu, Jul 29, 2010 at 11:01 AM, irfan irfannase...@gmail.com wrote: I attended Amazon placement test today . There was a question where i got confused.It is as follows. Give an algorithm to connect all nodes in one level of a binary tree . 5 5 / \ / \ 8 2 8 2 / \ / / \ / 1 2 61 --- 2 --6 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Sorry for that. I attached a jpg file showing what shud the algo do . Question is that, we are given a tree. algo shud connect all the nodes which are in same level. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] number of BST's
@amit is it BST or binary tree??cos BST is unique rite???binary tree meas use catalan numbers 2nCn/(n+1)! On Thu, Jul 29, 2010 at 9:56 PM, amit amitjaspal...@gmail.com wrote: Given the numbers from 1 to n, write an algorithm to find how many distinct binary search trees can be formed.. eg n=4, no of distinct bst's are 14. ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: a google question
I have formulated a solution, not strictly of O(n), but I guess it's close. === 1. for(int k=0;kn;k++) { 2 get_max_of_temp_array(maxVal,visited_index_of_A/*Va[i]*/,visited_index_of_b/*Vb[j]*/); 3. Print_Max_of( a[va[i]+1] +b[Vb[j]] , a[va[i]] + b[vb[j+1]] ,maxVal) 4 insert_other_two_of_the_triplet(); 5(i,j)=(index_of_maximum_value printed_above); 6 update_Va__Vb_accordingly(); } insert... on line 6 is to insert the (set-)element in an insertion-sorted array. But still not O(n). :( On Wed, Jul 28, 2010 at 4:11 PM, manish bhatia mb_mani...@yahoo.com wrote: I guess your solution would also be proved incorrect with the following, Numbers in bold are the two arrays. 125122 120 110 104 103 102 101 100 99 9897 130255 252 250 240 234 233 232 231 230 229 228 227 128253 250 248 238 232 231 230 229 228 227 226 225 126251 248 246 236 230 229 228 227 226 225 224 223 125250 247 245 235 229 228 227 226 225 224 223 222 105230 227 225 215 209 208 207 206 205 204 203 202 104229 226 224 214 208 207 206 205 204 203 202 201 103228 225 223 213 207 206 205 204 203 202 201 200 102227 224 222 212 206 205 204 203 202 201 200 199 101226 223 221 211 205 204 203 202 201 200 199 198 100225 222 220 210 204 203 202 201 200 199 198 197 99 224 221 219 209 203 202 201 200 199 198 197 196 98 224 221 219 209 203 202 201 200 199 198 197 196 manish... -- *From:* Varun Nagpal varun.nagp...@gmail.com *To:* Algorithm Geeks algogeeks@googlegroups.com *Sent:* Mon, 3 May, 2010 12:26:24 PM *Subject:* Re: [algogeeks] Re: a google question Guys no one commented on my solution? Any takes on it? Anyways, below is my solution (in pseudo code) Pre-condition: A and B are sequences of equal length and sorted in descending order Input: Sequences A[1..N] and B[1..N] of equal lengths(N) Ouput: Sequence C[1..N] containing sorted sum of ordered pairs from cartesian products of A, B or B,A Sort(A,B) { k = 1 N = length(A) = length(B) C[1..2*N] = []// Empty array cart_prod_order = 0 // 0 - AxB, 1 - BxA. 0 is default // Complexity : O(N) while(k != N+1) { if (A[k] B [k]) { cart_prod_order = 1 break } else { k = k + 1 } } // Choose the correct order of Cartesian product sum // Complexity: Theta(2N) = O(N) if (cart_prod_order == 1) { // take cartesian product of B and A, storing the sum of ordered pair (b,a) in each element of C C[1..2N] = B[1..2] x A[1..N] } else { // take cartesian product of A and B, storing the sum of ordered pair (a,b) in each element of C C[1..2N] = A[1..2] x B[1..N] } // Merge // C[1..N] and C[N+1..2N] are already sorted in descending order // Complexity: Theta(N) C[1..2N] = Merge(C[1..N],C[N+1..2N]) return C[1..N] } Merge(C,D) { i=1,j=1,k=1 E = [] while(i=length(C) OR j=length(D)) { if(i=length(C) AND (jlength(D) OR C[i]D[j])) { E[k] = C[i] i = i + 1 } else { E[k] = D[j] j = j + 1 } k = k + 1 } return E; } On Fri, Apr 30, 2010 at 7:50 PM, banu varun.nagp...@gmail.com wrote: Nice question: 1. |A| = |B| i.e I assume their cardinality is equal 2. A(n) = { a1, a2 a3, ...aN} such that a1=a2=a3...=aN 3. B(n) = { b1, b2 b3, ...bN} such that b1=b2=b3...=bN 4. S(n^2) = A x B = {(a1,b1), (a1,b2)(a1,bN), (a2,b1), (a2,b2)(a2,bN), (aN,b1), (aN,b2)(aN,bN)} assuming we have added in a way such that we find a pair ai bi, for some i in 1..N such that a(i-1) = b(i-1) A first observation is that in the worst case, the first 2N numbers in S will contain the final result of N numbers. i.e in (a1,b1), (a1,b2)(a1,bN), (a2,b1), (a2,b2)(a2,bN) In the best case first N numbers in S will contain the final N numbers (already sorted in decreasing order) i.e in (a1,b1), (a1,b2)(a1,bN) Now, if we consider again the worst case scenario, then we can first divide 2N numbers in two groups of size N each and each of this group is already sorted in decreasing order. i.e (a1,b1), (a1,b2)(a1,bN) and (a2,b1), (a2,b2)(a2,bN) Now we can simply apply Merge Algorithm on these 2 already sorted arrays of size N each in O(N) time, which solves the problem I can
Re: [algogeeks] Generate a number
If space is not a restriction- Build a B-tree. 1. Have a dummy root. 2. At level one- Numbers divisible by 1. ie. (1-9). 3. At level 2- numbers made after adding a digit to numbers at level 1. e.g. number 7 at level will have children- (70,72,74,76,78). and so on.. 4. Do the same at each level. Leaf nodes at level 10 will be your answers. I think math can optimize this a bit- though. On Thu, Jul 29, 2010 at 9:57 PM, amit amitjaspal...@gmail.com wrote: An algorithm to print all the 10-digit nos such that first 1 digit is divisible by 1, first 2 digits by 2, first 3 digits by 3 and so on...first 9 digits by 9. I think the tenth digit can be anything from 0 to 9. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] number of BST's
@AMIT: what does n represents? On Fri, Jul 30, 2010 at 5:46 AM, sharad kumar aryansmit3...@gmail.comwrote: @amit is it BST or binary tree??cos BST is unique rite???binary tree meas use catalan numbers 2nCn/(n+1)! On Thu, Jul 29, 2010 at 9:56 PM, amit amitjaspal...@gmail.com wrote: Given the numbers from 1 to n, write an algorithm to find how many distinct binary search trees can be formed.. eg n=4, no of distinct bst's are 14. ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
On 30 July 2010 02:59, Priyanka Chatterjee dona.1...@gmail.com wrote: Algo: 1. find height of tree 2. do level order traversal i at each level store the address of each tree node in the data part of a linked node and form linked list of the nodes ii store the header of a linked list at a certain level in an array 3. return array.// gives final structure complexity - T(n) =O(n) S(n)=O(h+n ) //h=height of tree //CODE //tree structure struct node { int data; struct node * left, *right}; // linked list structure struct linkNode{ struct node * data; struct linkNode * next; } struct linkNode** func(struct node * root){ struct linkNode ** array; int i, h=height(root); for(i=1;i=h;i++) array[i-1]=levelOrderTraversal(root, i); return array;// final tree structure } //max height of tree int height(struct node *root){ int hL=height(root-left); int hR=height(root-right); return 1+ HRHL?HR:HL; } struct nodelink* levelOrderTraversal(struct node*root, int level){ if(root==NULL) return NULL; if (level==1) return createLinkNode(root); // create a node of a singly l struct LinkNode *ptr; if(level1){ struct nodeLink * ptr1, *ptr2; ptr1=levelOrderTraversal(root-left,level-1); ptr2=levelOrderTraversal(root-right,level-1); if(ptr1==NULL ptr2==NULL) return NULL; if(ptr1==NULL) return ptr2; if(ptr2==NULL) return ptr1; ptr1-next=ptr2; return ptr2; } } struct linkNode * createLinkNode(struct node * root){ struct linkNode* newNode=(struct linkNode*) malloc(sizeof(struct linkNode)); newNode-data=root; newNode-next=NULL; } -- Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- Thanks Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.