[algogeeks] Amazon Interview Question
Q1) Given a newspaper and a set of ‘l’ words, give an efficient algorithm to find the ‘l’ words in the newspaper. Q2) Find the next higher number in set of permutations of a given number. Q3) Given preorder of a BST, find if each non-leaf node has just one child or not. To be done in linear time. Q4) Given a dictionary of words, two APIs Is_word(string) Is_prefix(string) And a NxN matrix with each postion consisting of a character. If from any position (i,j) you can move in any of the four directions, find out the all the valid words that can be formed in the matrix. (looping is not allowed, i.e. for forming a word position if you start from (i,j) and move to (i-1,j) then from this position you cannot go back to (i,j)) Q5) Given that there are n players and each one of them has played exactly one game with every other player. Also given is an API that tells whether player ‘a’ won or lost to player ‘b’, where ‘a’ and ‘b’ could be any of the players. Arrange the n players in a length n array such that player at position ‘i’ has won from player at ‘i+1’ and lost to player at ‘i-1’. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/LzG-OrtjDmoJ. To post to this group, send email to algogeeks@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] Permuatation of string in caase of duplicte string it shouldnt print duplicates permutation .
you can use flag[256]; now you just need to check loop: flag[str[i]]==0) { //swap() //permute function call //swap() flag[str[i]=1; } done On 7/3/12, Nishant Pandey nishant.bits.me...@gmail.com wrote: 1) Find all permutations of a string. 2) Improve it so that the permutations are not repeated, Eg= string is Answer should be just once not 4! times. i want suggestion to improve the recursive code in case of 2) case . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] Permuatation of string in caase of duplicte string it shouldnt print duplicates permutation .
you can use flag[256]; now you just need to check loop: if (flag[str[i]]==0) { //swap() //permute function call //swap() flag[str[i]=1; } done On 7/4/12, atul anand atul.87fri...@gmail.com wrote: you can use flag[256]; now you just need to check loop: flag[str[i]]==0) { //swap() //permute function call //swap() flag[str[i]=1; } done On 7/3/12, Nishant Pandey nishant.bits.me...@gmail.com wrote: 1) Find all permutations of a string. 2) Improve it so that the permutations are not repeated, Eg= string is Answer should be just once not 4! times. i want suggestion to improve the recursive code in case of 2) case . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] Write a C program to reconstruct a BST from a given array of preorder traversal.
u need inoder traversal as well On Wed, Jul 4, 2012 at 11:22 AM, Navin Kumar algorithm.i...@gmail.comwrote: -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/xmZH9KY72_IJ. To post to this group, send email to algogeeks@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. -- Vindhya Chhabra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] Write a C program to reconstruct a BST from a given array of preorder traversal.
@Vindhya: BST can be reconstructed only by preorder traversal. In case of binary tree we need two traversal inorder and pre/post order On Wed, Jul 4, 2012 at 1:07 PM, vindhya chhabra vindhyachha...@gmail.comwrote: u need inoder traversal as well On Wed, Jul 4, 2012 at 11:22 AM, Navin Kumar algorithm.i...@gmail.comwrote: -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/xmZH9KY72_IJ. To post to this group, send email to algogeeks@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. -- Vindhya Chhabra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] serialize a binary tree
Serialisation meaning? Numbering the nodes. Any specific order, or as in level order?? On 7/4/12, Ashish Goel ashg...@gmail.com wrote: a] How would you serialize a binary tree in a file(improve it) b] serialization that you have chosen, write a code to reconstruct the tree Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 Interview Question
1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote: Find the next higher number in set of permutations of a given number -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 Interview Question
Q5 is sorting problem Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote: Find the next higher number in set of permutations of a given number -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 Interview Question
Q4 vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { if (visited[i][j]) continue; visited[i][j] = true; String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote: Find the next higher number in set of permutations of a given number -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] serialize a binary tree
my understanding is to either write the level order traversal noting parent, child relation or write the adjacency list into a file where we store the edges Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 3:58 PM, adarsh kumar algog...@gmail.com wrote: Serialisation meaning? Numbering the nodes. Any specific order, or as in level order?? On 7/4/12, Ashish Goel ashg...@gmail.com wrote: a] How would you serialize a binary tree in a file(improve it) b] serialization that you have chosen, write a code to reconstruct the tree Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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 Interview Question
Consider trees: 1 3 2 3 2 1 pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't satisfy the criteria . So I don't think it can be determined. On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote: Q4 vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { if (visited[i][j]) continue; visited[i][j] = true; String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.com wrote: Find the next higher number in set of permutations of a given number -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Thanks regards Bhupendra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 Interview Question
1. For first question trie of given word will be best option. Space complexity O(total length of words) (worst case) Time complexity O(T) . T length of input text (Newspaper) 2. consider it to be a 4 digit number ABCD . Find maximum Most significant digit say it is C , and out of these nos find maximum value of next digit say A and so on . Suppose Final no. is CADB Now next highest permutation will be the no. just greater than this and made of these digits . This is easy. On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey bhupendra@gmail.comwrote: Consider trees: 1 3 2 3 2 1 pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't satisfy the criteria . So I don't think it can be determined. On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote: Q4 vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { if (visited[i][j]) continue; visited[i][j] = true; String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote: Find the next higher number in set of permutations of a given number -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Thanks regards Bhupendra -- Thanks regards Bhupendra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] serialize a binary tree
we can serialize the binary tree using preorder traversal and marking NULL pointer as '#'. source: http://www.leetcode.com/2010/09/serializationdeserialization-of-binary.html On Wed, Jul 4, 2012 at 4:21 PM, Ashish Goel ashg...@gmail.com wrote: my understanding is to either write the level order traversal noting parent, child relation or write the adjacency list into a file where we store the edges Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 3:58 PM, adarsh kumar algog...@gmail.com wrote: Serialisation meaning? Numbering the nodes. Any specific order, or as in level order?? On 7/4/12, Ashish Goel ashg...@gmail.com wrote: a] How would you serialize a binary tree in a file(improve it) b] serialization that you have chosen, write a code to reconstruct the tree Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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 algogeeks@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 Interview Question
For question 5. Even this doesn't seems right Consider this scenario Match b/w Winner a vs b a a vs c c b vs c b What will be order ?? acb or bca On Wed, Jul 4, 2012 at 5:38 PM, Bhupendra Dubey bhupendra@gmail.comwrote: 1. For first question trie of given word will be best option. Space complexity O(total length of words) (worst case) Time complexity O(T) . T length of input text (Newspaper) 2. consider it to be a 4 digit number ABCD . Find maximum Most significant digit say it is C , and out of these nos find maximum value of next digit say A and so on . Suppose Final no. is CADB Now next highest permutation will be the no. just greater than this and made of these digits . This is easy. On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey bhupendra@gmail.comwrote: Consider trees: 1 3 2 3 2 1 pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't satisfy the criteria . So I don't think it can be determined. On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote: Q4 vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { if (visited[i][j]) continue; visited[i][j] = true; String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote: Find the next higher number in set of permutations of a given number -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Thanks regards Bhupendra -- Thanks regards Bhupendra -- Thanks regards Bhupendra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: Write a C program to reconstruct a BST from a given array of preorder traversal.
Vindhya - Navin is right because in case of BST, if you sort the preorder array you will get inorder array. This means you already have information about the inorder, if you given preorder/postorder/levelorder. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/RxgCU_O2m9kJ. To post to this group, send email to algogeeks@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] balanced tree
bool checkTree(Tree node) { if(node[right]==NULLnode[left]==NULL) return true; if(node[right]==NULLnode[left]!=NULL||node[left]==NULLnode[right]!=NULL) return false; else return checkTree(node[right])checkTree(node[left]); } i think this algo can solve problem just traverse the node and keep eye on that either a node have 2 childs or no child On Wed, Jul 4, 2012 at 3:08 PM, Ashish Goel ashg...@gmail.com wrote: i think checking full is easy, find height(0to h) and then check if level h has 2^(h+1) nodes how to check if it is complete..level order traversal? ensure that every node has two children or left for the last one just before first leaf( till you find the first leaf). Now on, every node should be a leaf. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 2:36 PM, Ashish Goel ashg...@gmail.com wrote: ok, lets modify the problem to find if the tree is complete binary tree The tree is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 11:09 AM, atul anand atul.87fri...@gmail.comwrote: http://www.geeksforgeeks.org/archives/5230 modify this to meet the requirnment. On 7/4/12, Ashish Goel ashg...@gmail.com wrote: WAP to find if a tree is balanced/fully balanced? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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. -- Thanks Regards Amritpal singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] balanced tree
int treeMaxHeight(int index) { if(tree[index]==NULL) return 0; else { return 1+max(treeHeight(2*index),treeHeight(2*index+1)); } } int treeMinHeight(int index) { if(tree[index]==NULL) return 0; else { return 1+min(treeHeight(2*index),treeHeight(2*index+1)); } } if(treeMaxHeight(1)-treeMinHeight(1)1) then not balanced; else Balanced; On Wed, Jul 4, 2012 at 8:53 AM, Ashish Goel ashg...@gmail.com wrote: WAP to find if a tree is balanced/fully balanced? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Thanks Regards Amritpal singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 Interview Question
1 2 3 is not a BST and its pre-order traversal is 1 2 3, pre order of other is 3 2 1 . On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey bhupendra@gmail.comwrote: Consider trees: 1 3 2 3 2 1 pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't satisfy the criteria . So I don't think it can be determined. On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote: Q4 vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { if (visited[i][j]) continue; visited[i][j] = true; String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote: Find the next higher number in set of permutations of a given number -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Thanks regards Bhupendra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] Permuatation of string in caase of duplicte string it shouldnt print duplicates permutation .
the code works fine only in case of duplicates , but if we consider string to be non duplicates like say :abc then all permutation cant be obtainned . On Wed, Jul 4, 2012 at 12:31 PM, atul anand atul.87fri...@gmail.com wrote: you can use flag[256]; now you just need to check loop: if (flag[str[i]]==0) { //swap() //permute function call //swap() flag[str[i]=1; } done On 7/4/12, atul anand atul.87fri...@gmail.com wrote: you can use flag[256]; now you just need to check loop: flag[str[i]]==0) { //swap() //permute function call //swap() flag[str[i]=1; } done On 7/3/12, Nishant Pandey nishant.bits.me...@gmail.com wrote: 1) Find all permutations of a string. 2) Improve it so that the permutations are not repeated, Eg= string is Answer should be just once not 4! times. i want suggestion to improve the recursive code in case of 2) case . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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: Write a C program to reconstruct a BST from a given array of preorder traversal.
^ Thank you! Mind discussing the algorithm please? On Wed, Jul 4, 2012 at 7:06 PM, deepikaanand swinyanand...@gmail.comwrote: code :- http://ideone.com/O5yuo -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] Permuatation of string in caase of duplicte string it shouldnt print duplicates permutation .
http://stackoverflow.com/questions/1900197/generating-variations-without-repetitions-permutations-in-java/ On Wed, Jul 4, 2012 at 8:16 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: the code works fine only in case of duplicates , but if we consider string to be non duplicates like say :abc then all permutation cant be obtainned . On Wed, Jul 4, 2012 at 12:31 PM, atul anand atul.87fri...@gmail.comwrote: you can use flag[256]; now you just need to check loop: if (flag[str[i]]==0) { //swap() //permute function call //swap() flag[str[i]=1; } done On 7/4/12, atul anand atul.87fri...@gmail.com wrote: you can use flag[256]; now you just need to check loop: flag[str[i]]==0) { //swap() //permute function call //swap() flag[str[i]=1; } done On 7/3/12, Nishant Pandey nishant.bits.me...@gmail.com wrote: 1) Find all permutations of a string. 2) Improve it so that the permutations are not repeated, Eg= string is Answer should be just once not 4! times. i want suggestion to improve the recursive code in case of 2) case . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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. -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] Finding intersection of 2 linked lists
Any efficient algorithm to find intersection of two linked lists.Example: Linked List 1) 1 - 2 - 3 - 4 - 5 - 6 Linked List 2) 3 - 4 - 5 Intersection 4 - 5 - 6 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/-8_lnGA-ZhgJ. To post to this group, send email to algogeeks@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] simple FILE reading problem.
Suppose a file.txt contains : 50 40 30 # # 5 # 10 # # i want to fetch only integers. How should i fetch it. I tried with fgetc and fscanf but it was too complicated. My approach: fetched one word at a time and put it into separate string and then i converted that string to integer(if each character of that string was between '0' to '9'). Is there any simple way to do this. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/btvudXnBrAIJ. To post to this group, send email to algogeeks@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] simple FILE reading problem.
Fetch a character. if isdigit( current_character ) flag =1 else if current_character is any character except space while current_char is not space current_char_position ++ On Wed, Jul 4, 2012 at 10:44 PM, Navin Kumar algorithm.i...@gmail.comwrote: Suppose a file.txt contains : 50 40 30 # # 5 # 10 # # i want to fetch only integers. How should i fetch it. I tried with fgetc and fscanf but it was too complicated. My approach: fetched one word at a time and put it into separate string and then i converted that string to integer(if each character of that string was between '0' to '9'). Is there any simple way to do this. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/btvudXnBrAIJ. To post to this group, send email to algogeeks@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. -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] simple FILE reading problem.
Please ignore the last post Fetch a character. if isdigit( current_character ) add it to temp string flag =1 else if current_character is any character except space flag = 0 while current_char is not space current_char_position ++ else if current_char is space and flag = 1 fetch last word (temp string) On Wed, Jul 4, 2012 at 10:51 PM, Abhishek Sharma abhi120...@gmail.comwrote: Fetch a character. if isdigit( current_character ) flag =1 else if current_character is any character except space while current_char is not space current_char_position ++ On Wed, Jul 4, 2012 at 10:44 PM, Navin Kumar algorithm.i...@gmail.comwrote: Suppose a file.txt contains : 50 40 30 # # 5 # 10 # # i want to fetch only integers. How should i fetch it. I tried with fgetc and fscanf but it was too complicated. My approach: fetched one word at a time and put it into separate string and then i converted that string to integer(if each character of that string was between '0' to '9'). Is there any simple way to do this. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/btvudXnBrAIJ. To post to this group, send email to algogeeks@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. -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] Finding intersection of 2 linked lists
it was 4 - 5, not 4 - 5 - 6 On Wed, Jul 4, 2012 at 10:41 PM, Abhi abhi120...@gmail.com wrote: Any efficient algorithm to find intersection of two linked lists.Example: Linked List 1) 1 - 2 - 3 - 4 - 5 - 6 Linked List 2) 3 - 4 - 5 Intersection 4 - 5 - 6 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/-8_lnGA-ZhgJ. To post to this group, send email to algogeeks@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. -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] Finding intersection of 2 linked lists
3 - 4 - 5, sorry for that silly mistakes On Wed, Jul 4, 2012 at 10:54 PM, Abhishek Sharma abhi120...@gmail.comwrote: it was 4 - 5, not 4 - 5 - 6 On Wed, Jul 4, 2012 at 10:41 PM, Abhi abhi120...@gmail.com wrote: Any efficient algorithm to find intersection of two linked lists.Example: Linked List 1) 1 - 2 - 3 - 4 - 5 - 6 Linked List 2) 3 - 4 - 5 Intersection 4 - 5 - 6 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/-8_lnGA-ZhgJ. To post to this group, send email to algogeeks@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. -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] simple FILE reading problem.
reading from a file is bottle neck so better to read number of line into a buffer then read it char by char or word by word depend on algo... On Wed, Jul 4, 2012 at 10:44 PM, Navin Kumar algorithm.i...@gmail.comwrote: Suppose a file.txt contains : 50 40 30 # # 5 # 10 # # i want to fetch only integers. How should i fetch it. I tried with fgetc and fscanf but it was too complicated. My approach: fetched one word at a time and put it into separate string and then i converted that string to integer(if each character of that string was between '0' to '9'). Is there any simple way to do this. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/btvudXnBrAIJ. To post to this group, send email to algogeeks@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. -- Thanks Regards Amritpal singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 Interview Question
Sorry i typed wrongly tree is 2 1 3 preorder traversal is 123 and same for other tree as well. Please check ! On Wed, Jul 4, 2012 at 5:24 PM, a g ag20071...@gmail.com wrote: 1 2 3 is not a BST and its pre-order traversal is 1 2 3, pre order of other is 3 2 1 . On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey bhupendra@gmail.comwrote: Consider trees: 1 3 2 3 2 1 pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't satisfy the criteria . So I don't think it can be determined. On Wed, Jul 4, 2012 at 4:16 PM, Ashish Goel ashg...@gmail.com wrote: Q4 vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { if (visited[i][j]) continue; visited[i][j] = true; String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote: 1. inverted hasp map 2. not clear 3. VLR, how do you identify end of L and start of R, question incomplete 4. One problem: consider ... a b... c d... ... if ab is a prefix, can aba be another prefix, i would assume so. But if that is true, i am not sure if this program will come to an end. vectorString prefix; prefix[0]=NULL; prefixCount =1; for (int i=0;in;i++) for (int j=0;jn;j++) for (int k=0; kprefixCount;k++) { String s=prefix[k]+a[i][j]; if (isWord(s) { printWord(s); prefix[k]=s; continue;} else if isPrefix(s) prefix[prefixCount++] = s; else removePrefix(prefix[k], prefixCount); prefix[prefixCount++] = String(a[i][j]; } Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Wed, Jul 4, 2012 at 12:22 PM, Decipher ankurseth...@gmail.comwrote: Find the next higher number in set of permutations of a given number -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Thanks regards Bhupendra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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. -- Thanks regards Bhupendra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: Write a C program to reconstruct a BST from a given array of preorder traversal.
thanks all On Wed, Jul 4, 2012 at 10:57 PM, Navin Gupta navin.nit...@gmail.com wrote: Given a pre-order traversal, we can sort it to get the inorde traversal. Sorting the preorder is O( NLogN ). Now as we know the ordering of elements is Preorder - Root - Left Child - Right Child Inorder - Left Child - Root - Right Child 1The first element in Pre-order traversal is root of tree. 2find its index in the inorder traversal ( I ) . 3All the elements to the left of root in inorder traversal consist Left-Subtree ( IL ) of the root while those to the right consist Right-Subtree ( IR ) of the root. 4Perform the steps 1-3 recursively for the IL IR. Searching is LogN, so constructing the entire tree is O(NLogN). Even though we can use hash to get O(1) search complexity. But still sorting the preorder to get inorder is O ( NLogN ). -- Navin Kumar Gupta Final Year,B.Tech(Hons.) Computer Science Engg. National Institute of Technology,Jamshedpur Mobile - (+91)8285303045 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/wmkx-kDe3EEJ. To post to this group, send email to algogeeks@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. -- Vindhya Chhabra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: Write a C program to reconstruct a BST from a given array of preorder traversal.
@Navin I dont think der is any need to sort the preorder traversal given ...it will cost u more as sorting take O(n log n ) and recursion alone will take O(n^2) {mentioned in step 4 } sO the overall complexity will be the sum of two..+ space of O(n) //to store inorder traversal -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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] Finding intersection of 2 linked lists
get the size of both the linked list say d1,d2 ; get their diff like df=abs(d1-d2); now take 2 pointers both poiting to the start of both the linked list . go to bigger list now move this pointer until both the distance becomes equal . at this point we have one pointer from smaller list pointing to the start of the list and another pointer in bigger list pointing to node where distance came equal , move these 2 pointers until both point to the same node .. and we are done . On Wed, Jul 4, 2012 at 10:44 PM, Amit Chauhan amitchauhan@gmail.comwrote: If both the linked list are ordered one then you can solve this problem in linear time and with constant space. On Wed, Jul 4, 2012 at 10:41 PM, Abhi abhi120...@gmail.com wrote: Any efficient algorithm to find intersection of two linked lists.Example: Linked List 1) 1 - 2 - 3 - 4 - 5 - 6 Linked List 2) 3 - 4 - 5 Intersection 4 - 5 - 6 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/-8_lnGA-ZhgJ. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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.