Re: [algogeeks] Microsoft written test question
while doing in-order traversal, we have to check if(prev current) -- then mark prev element for swapping in the first time violation.. if it happens for the second time..then mark current element for swapping. swap both .. If we don't get the violation for the second time .. means both are side-by-side elements .. swap them .. Hope works .. If I miss any case .. correct me thanks, On Sun, Sep 2, 2012 at 7:45 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @navin: can u explain ur algorithms in words pls.. On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar algorithm.i...@gmail.comwrote: void correctBST(struct node *root) { int flag =0; static struct node *temp1, *temp2, *temp3, *prev; static int found; if(found) return; if(root) { correctBST(root-left); if(!temp1 prev root-data prev-data) { temp1 = prev; temp2 = root; swap((temp1-data), (temp2-data)); flag = 1; prev = temp1; } else if(!temp3 prev root-data prev-data) { temp3 = root; swap((temp1-data), (temp2-data)); swap((temp1-data), (temp3-data)); found = 1; return; } if(!flag) prev = root; correctBST(root-right); } } On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: help to solve the following.. Question: Two of the nodes of a BST are swapped. Correct the BST (taken from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd online test 3rd question) -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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 and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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] string matching problem
above link was for reference , extending the logic was obvious :) :) On Mon, Sep 3, 2012 at 11:22 AM, bharat b bagana.bharatku...@gmail.comwrote: @atul: question is to find the largest continuous sub array .. not just continuous sub array .. we can do this with same logic as mentioned in the above link.. we have to traverse whole array.. even if we get the solution .. whenever we get the solution,update the largest_subarray_start_index and largest_subarray_end_index based on previous length of the solution sub array . On Mon, Sep 3, 2012 at 9:26 AM, atul anand atul.87fri...@gmail.comwrote: http://www.geeksforgeeks.org/archives/19267 On Mon, Sep 3, 2012 at 7:41 AM, Amitesh Singh singh.amit...@gmail.comwrote: Given a array, find the largest contiguous sub-array having its sum equal to N. -- 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] string matching problem
why can't we change the question to sum=0 .. On Mon, Sep 3, 2012 at 12:57 PM, atul anand atul.87fri...@gmail.com wrote: above link was for reference , extending the logic was obvious :) :) On Mon, Sep 3, 2012 at 11:22 AM, bharat b bagana.bharatku...@gmail.comwrote: @atul: question is to find the largest continuous sub array .. not just continuous sub array .. we can do this with same logic as mentioned in the above link.. we have to traverse whole array.. even if we get the solution .. whenever we get the solution,update the largest_subarray_start_index and largest_subarray_end_index based on previous length of the solution sub array . On Mon, Sep 3, 2012 at 9:26 AM, atul anand atul.87fri...@gmail.comwrote: http://www.geeksforgeeks.org/archives/19267 On Mon, Sep 3, 2012 at 7:41 AM, Amitesh Singh singh.amit...@gmail.comwrote: Given a array, find the largest contiguous sub-array having its sum equal to N. -- 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. -- 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] MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.
@Dave : algo seems fine...but it seems to me that it would difficult to maintain both left to right and right to left parallel way :( :( . it would be gr8 if you can provided little bit of coded algorithm for it. On Mon, Sep 3, 2012 at 10:36 AM, Dave dave_and_da...@juno.com wrote: @Atul007: No need to destroy the BST. Perform two simultaneous inorder traversals of the BST, one from left to right (the usual direction) and one from right to left. At any stage you have selected two nodes. If the sum is less than the given number, advance the left-to-right traversal; If the sum is greater, advance the right-to-left traversal. Quit with success when the sum equals the given number or with failure when the two traversals have reached the same node. Dave On Sunday, September 2, 2012 11:00:42 PM UTC-5, atul007 wrote: convert BST to sorted DLL.. now it is a double linked list , so we can find 2 number in O(n) time by keeping 2 pointers(one at start and one at end) from sorted DLL. now convert DLL to BST. On Mon, Sep 3, 2012 at 1:32 AM, Navin Kumar algorit...@gmail.com wrote: MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space. -- 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/-/oizd-5CSfuoJ. 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] MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.
what is right to left inorder? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Sep 3, 2012 at 1:13 PM, atul anand atul.87fri...@gmail.com wrote: @Dave : algo seems fine...but it seems to me that it would difficult to maintain both left to right and right to left parallel way :( :( . it would be gr8 if you can provided little bit of coded algorithm for it. On Mon, Sep 3, 2012 at 10:36 AM, Dave dave_and_da...@juno.com wrote: @Atul007: No need to destroy the BST. Perform two simultaneous inorder traversals of the BST, one from left to right (the usual direction) and one from right to left. At any stage you have selected two nodes. If the sum is less than the given number, advance the left-to-right traversal; If the sum is greater, advance the right-to-left traversal. Quit with success when the sum equals the given number or with failure when the two traversals have reached the same node. Dave On Sunday, September 2, 2012 11:00:42 PM UTC-5, atul007 wrote: convert BST to sorted DLL.. now it is a double linked list , so we can find 2 number in O(n) time by keeping 2 pointers(one at start and one at end) from sorted DLL. now convert DLL to BST. On Mon, Sep 3, 2012 at 1:32 AM, Navin Kumar algorit...@gmail.comwrote: MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space. -- 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/-/oizd-5CSfuoJ. 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] BST to DLL code: whats wrong with this code........
if u r getting desired output ? then what is the problem? On Sun, Sep 2, 2012 at 7:24 PM, shubham jain coolshubham...@gmail.comwrote: Hi I am trying to convert the BST to doubly linked list but I am getting desired output with this code Plz correct this code. #includestdio.h #includestdlib.h typedef struct tree mytree; struct tree { int data; mytree* left; mytree* right; }; void insert(mytree** root,int data) { if(*root==NULL) { mytree* node=(mytree*)malloc(sizeof(mytree)); if(node==NULL) return; else { node-data=data; node-left=NULL; node-right=NULL; } *root=node; return; } else { if((*root)-data =data) insert((*root)-left,data); else insert((*root)-right,data); } } void traverse(mytree* ptr) { if(ptr==NULL) return; traverse(ptr-left); printf(%d\t,ptr-data); traverse(ptr-right); } void traversell(mytree* ptr) { if(ptr==NULL) return; while(ptr!=NULL) { printf(%d\t,ptr-data); ptr=ptr-right; } } void bst22ll(mytree** tree,mytree** head) { static mytree* prev=NULL; if(*tree==NULL) return; mytree* ptr=*tree; if((*tree)-left!=NULL) bst22ll((*tree)-left,head); *tree=ptr; if(*head==NULL) { *head=*tree; (*head)-left==NULL; } else { prev-right=*tree; (*tree)-left=prev; } prev=*tree; if((*tree)-right!=NULL) { bst22ll((*tree)-right,head); } } void bst2ll(mytree** tree) { if(tree==NULL) return; mytree* head=NULL; mytree* prev=NULL; bst22ll(tree,head); *tree=head; } int main() { mytree* tree=NULL; insert(tree,50); insert(tree,40); insert(tree,60); insert(tree,30); insert(tree,70); insert(tree,65); insert(tree,45); insert(tree,34); traverse(tree); bst2ll(tree); printf(\n); traversell(tree); printf(\n); } should print : 30 34 40 45 50 60 65 70 but printing: 30 34 40 45 50 60 70 Thank you Shubham -- 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/-/XXMvBSg0t08J. 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. -- With regards, Manish kumar untwal Indian Institute of Information Technology Allahabad (2009-2013 batch) -- 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] MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.
@dave same doubt as @atul, how we can manage both function parallel and to all can we traverse a tree using some looping instead of traditional recursive methods..?? On Mon, Sep 3, 2012 at 1:13 PM, atul anand atul.87fri...@gmail.com wrote: @Dave : algo seems fine...but it seems to me that it would difficult to maintain both left to right and right to left parallel way :( :( . it would be gr8 if you can provided little bit of coded algorithm for it. On Mon, Sep 3, 2012 at 10:36 AM, Dave dave_and_da...@juno.com wrote: @Atul007: No need to destroy the BST. Perform two simultaneous inorder traversals of the BST, one from left to right (the usual direction) and one from right to left. At any stage you have selected two nodes. If the sum is less than the given number, advance the left-to-right traversal; If the sum is greater, advance the right-to-left traversal. Quit with success when the sum equals the given number or with failure when the two traversals have reached the same node. Dave On Sunday, September 2, 2012 11:00:42 PM UTC-5, atul007 wrote: convert BST to sorted DLL.. now it is a double linked list , so we can find 2 number in O(n) time by keeping 2 pointers(one at start and one at end) from sorted DLL. now convert DLL to BST. On Mon, Sep 3, 2012 at 1:32 AM, Navin Kumar algorit...@gmail.comwrote: MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space. -- 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/-/oizd-5CSfuoJ. 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 and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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: give the algo or program to find second largest element in a list using tournament method
@bharat is it tournament method?? On Mon, Sep 3, 2012 at 2:34 PM, bharat b bagana.bharatku...@gmail.comwrote: Construct a max-heap -- O(n).. call delete() 2 times .. -- O(logn).. === O(n) time.. On Fri, Aug 31, 2012 at 1:46 AM, Don dondod...@gmail.com wrote: While the list length is more than one Take 2 elements from the head Select the larger of the two If the smaller is greater than the largest beaten by the larger Then set the largest beaten by the larger to the value of the smaller Add the larger to the tail of the list When this completes, you'll have one element containing the largest and second largest values. typedef struct { unsigned int value; unsigned int largestBeaten; } element; unsigned int secondLargest(queueelement elements) { while(elements.length() 1) { element A = elements.dequeue(); element B = elements.dequeue(); if (A.value B.value) swap(A,B); if (A.largestBeaten B.value) A.largestBeaten = B.value; elements.enqueue(A); } return queue.head().largestBeaten; } On Aug 30, 12:53 pm, sangeeta goyal sangeeta15...@gmail.com wrote: @Don can you give the algorithm for the same?? how would you implement it?? On Thu, Aug 30, 2012 at 10:03 PM, Don dondod...@gmail.com wrote: The second largest element is the largest element beaten by the winner. So if you implement a tournament in which each element keeps track of the largest element it has beaten, you'll get the second largest naturally. Don On Aug 29, 9:15 am, Sangeeta sangeeta15...@gmail.com wrote: give the algo or program to find second largest element in a list using tournament method -- 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] MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.
@ashish : i.e in decreasing order inorder(root) if not null inorder(root-right); inorder(root-left); On Mon, Sep 3, 2012 at 4:35 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @dave same doubt as @atul, how we can manage both function parallel and to all can we traverse a tree using some looping instead of traditional recursive methods..?? On Mon, Sep 3, 2012 at 1:13 PM, atul anand atul.87fri...@gmail.comwrote: @Dave : algo seems fine...but it seems to me that it would difficult to maintain both left to right and right to left parallel way :( :( . it would be gr8 if you can provided little bit of coded algorithm for it. On Mon, Sep 3, 2012 at 10:36 AM, Dave dave_and_da...@juno.com wrote: @Atul007: No need to destroy the BST. Perform two simultaneous inorder traversals of the BST, one from left to right (the usual direction) and one from right to left. At any stage you have selected two nodes. If the sum is less than the given number, advance the left-to-right traversal; If the sum is greater, advance the right-to-left traversal. Quit with success when the sum equals the given number or with failure when the two traversals have reached the same node. Dave On Sunday, September 2, 2012 11:00:42 PM UTC-5, atul007 wrote: convert BST to sorted DLL.. now it is a double linked list , so we can find 2 number in O(n) time by keeping 2 pointers(one at start and one at end) from sorted DLL. now convert DLL to BST. On Mon, Sep 3, 2012 at 1:32 AM, Navin Kumar algorit...@gmail.comwrote: MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space. -- 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/-/oizd-5CSfuoJ. 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 and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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] BST to DLL code: whats wrong with this code........
Sorry by mistake i write that Actually I am not getting desired output.. On Mon, Sep 3, 2012 at 11:02 AM, manish untwal manishuntw...@gmail.comwrote: if u r getting desired output ? then what is the problem? On Sun, Sep 2, 2012 at 7:24 PM, shubham jain coolshubham...@gmail.comwrote: Hi I am trying to convert the BST to doubly linked list but I am getting desired output with this code Plz correct this code. #includestdio.h #includestdlib.h typedef struct tree mytree; struct tree { int data; mytree* left; mytree* right; }; void insert(mytree** root,int data) { if(*root==NULL) { mytree* node=(mytree*)malloc(sizeof(mytree)); if(node==NULL) return; else { node-data=data; node-left=NULL; node-right=NULL; } *root=node; return; } else { if((*root)-data =data) insert((*root)-left,data); else insert((*root)-right,data); } } void traverse(mytree* ptr) { if(ptr==NULL) return; traverse(ptr-left); printf(%d\t,ptr-data); traverse(ptr-right); } void traversell(mytree* ptr) { if(ptr==NULL) return; while(ptr!=NULL) { printf(%d\t,ptr-data); ptr=ptr-right; } } void bst22ll(mytree** tree,mytree** head) { static mytree* prev=NULL; if(*tree==NULL) return; mytree* ptr=*tree; if((*tree)-left!=NULL) bst22ll((*tree)-left,head); *tree=ptr; if(*head==NULL) { *head=*tree; (*head)-left==NULL; } else { prev-right=*tree; (*tree)-left=prev; } prev=*tree; if((*tree)-right!=NULL) { bst22ll((*tree)-right,head); } } void bst2ll(mytree** tree) { if(tree==NULL) return; mytree* head=NULL; mytree* prev=NULL; bst22ll(tree,head); *tree=head; } int main() { mytree* tree=NULL; insert(tree,50); insert(tree,40); insert(tree,60); insert(tree,30); insert(tree,70); insert(tree,65); insert(tree,45); insert(tree,34); traverse(tree); bst2ll(tree); printf(\n); traversell(tree); printf(\n); } should print : 30 34 40 45 50 60 65 70 but printing: 30 34 40 45 50 60 70 Thank you Shubham -- 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/-/XXMvBSg0t08J. 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. -- With regards, Manish kumar untwal Indian Institute of Information Technology Allahabad (2009-2013 batch) -- 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] Microsoft written test question
@bharat: +1 i have tried some test cases.. working finely.. @anyone pls verify?? On Mon, Sep 3, 2012 at 11:58 AM, bharat b bagana.bharatku...@gmail.comwrote: while doing in-order traversal, we have to check if(prev current) -- then mark prev element for swapping in the first time violation.. if it happens for the second time..then mark current element for swapping. swap both .. If we don't get the violation for the second time .. means both are side-by-side elements .. swap them .. Hope works .. If I miss any case .. correct me thanks, On Sun, Sep 2, 2012 at 7:45 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @navin: can u explain ur algorithms in words pls.. On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar algorithm.i...@gmail.comwrote: void correctBST(struct node *root) { int flag =0; static struct node *temp1, *temp2, *temp3, *prev; static int found; if(found) return; if(root) { correctBST(root-left); if(!temp1 prev root-data prev-data) { temp1 = prev; temp2 = root; swap((temp1-data), (temp2-data)); flag = 1; prev = temp1; } else if(!temp3 prev root-data prev-data) { temp3 = root; swap((temp1-data), (temp2-data)); swap((temp1-data), (temp3-data)); found = 1; return; } if(!flag) prev = root; correctBST(root-right); } } On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: help to solve the following.. Question: Two of the nodes of a BST are swapped. Correct the BST (taken from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd online test 3rd question) -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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 and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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 and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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] MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.
@all: If we are doing inorder traversal , it will automatically take O(n) space for internal stack. On Mon, Sep 3, 2012 at 5:17 PM, atul anand atul.87fri...@gmail.com wrote: @ashish : i.e in decreasing order inorder(root) if not null inorder(root-right); inorder(root-left); On Mon, Sep 3, 2012 at 4:35 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @dave same doubt as @atul, how we can manage both function parallel and to all can we traverse a tree using some looping instead of traditional recursive methods..?? On Mon, Sep 3, 2012 at 1:13 PM, atul anand atul.87fri...@gmail.comwrote: @Dave : algo seems fine...but it seems to me that it would difficult to maintain both left to right and right to left parallel way :( :( . it would be gr8 if you can provided little bit of coded algorithm for it. On Mon, Sep 3, 2012 at 10:36 AM, Dave dave_and_da...@juno.com wrote: @Atul007: No need to destroy the BST. Perform two simultaneous inorder traversals of the BST, one from left to right (the usual direction) and one from right to left. At any stage you have selected two nodes. If the sum is less than the given number, advance the left-to-right traversal; If the sum is greater, advance the right-to-left traversal. Quit with success when the sum equals the given number or with failure when the two traversals have reached the same node. Dave On Sunday, September 2, 2012 11:00:42 PM UTC-5, atul007 wrote: convert BST to sorted DLL.. now it is a double linked list , so we can find 2 number in O(n) time by keeping 2 pointers(one at start and one at end) from sorted DLL. now convert DLL to BST. On Mon, Sep 3, 2012 at 1:32 AM, Navin Kumar algorit...@gmail.comwrote: MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space. -- 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/-/oizd-5CSfuoJ. 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 and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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] maximum length subarray with sum=0
@atul: i didnt get your algo fully.. Can u just tell me how it works on this array.. {-3 2 1 5 -12 6 1 -2} the aux array would become {-3 -1 0 5 -7 -1 0 -2} then whats the next step.? We analyze the aux for the repeated element which sets subarray start= 2 subarray end=6 then aux contains 0 at two indices 2 and 6.this gives us the correct answer here.. but that wont be the case everytime, right..? everytime start of subarray cant be 0.. Can u clarify more on this..? Coz i dont think it works on every test array.. On Sun, Sep 2, 2012 at 12:32 AM, atul anand atul.87fri...@gmail.com wrote: take aux[] array of same size and store cumulative some at aux[i]=sum{input[0 to i]} now if you find any repeated element at index i and j then, subarray start = i + 1; subarray end = j if array contain 0 at index j then, subarray start = 0; subarray end = j On 9/2/12, Puneet Gautam puneet.nsi...@gmail.com wrote: Given an array of positive and negative integers, we need to find the MAX length subarray having sum as ZERO... Is there a solution less than O(n^2)..? Please help .. i m stuck at this problem.. Thanks Puneet -- 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] use of static
Thats ok.. but can u tell me its more implementations in C and OOP..? On Sun, Sep 2, 2012 at 9:59 AM, rahul rahulr...@gmail.com wrote: i m talking in contest of question, not explaining overall picture of static in c,c++,java. On Sep 2, 2012 12:07 AM, Puneet Gautam puneet.nsi...@gmail.com wrote: @rahul: There is something more to static than to retain old value. Are u sure it is not used anywhere else for any other purpose, bcoz i dont think thats the whole purpose of this keyword.. On 8/30/12, rahul rahulr...@gmail.com wrote: static doing nothing, just to make a candidate confuse in interview. static comes into picture, when u calling same function again and again and u need some variable to retain the old value, and another scenario when u have to define the scope of variable. On Thu, Aug 30, 2012 at 6:02 PM, Puneet Gautam puneet.nsi...@gmail.comwrote: Well, its gives error in every array assignment..ISO forbids this type of assignment. @rahul: But whats with the static here. how does it affect any string declared..? I couldnt get your answer ..pls explain On Thu, Aug 30, 2012 at 12:54 PM, rahul rahulr...@gmail.com wrote: old style C, where you can't have auto array. just that. On Thu, Aug 30, 2012 at 12:52 PM, Romil ... vamosro...@gmail.comwrote: It should give an error in the line names[3] = names[4] These are fixed address values..you cannot change them. On Thu, Aug 30, 2012 at 12:44 PM, Puneet Gautam puneet.nsi...@gmail.com wrote: #includeiostream.h int main() {static char names[5][20]={pascal,ada,cobol,fortran,perl}; int i; char *t; t=names[3]; names[3]=names[4]; names[4]=t; for (i=0;i=4;i++) coutnames[i]endl; getchar(); return 0; } Whats the importance of static keyword here..? -- 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. -- Romil Software Engineer, Winshuttle Softwares India Pvt. Ltd. Chandigarh -- 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. -- 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] MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.
@navin : if O(n) recursive stack is not allowed then i wonder how can it can be solved. On 9/3/12, Navin Kumar algorithm.i...@gmail.com wrote: @all: If we are doing inorder traversal , it will automatically take O(n) space for internal stack. On Mon, Sep 3, 2012 at 5:17 PM, atul anand atul.87fri...@gmail.com wrote: @ashish : i.e in decreasing order inorder(root) if not null inorder(root-right); inorder(root-left); On Mon, Sep 3, 2012 at 4:35 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @dave same doubt as @atul, how we can manage both function parallel and to all can we traverse a tree using some looping instead of traditional recursive methods..?? On Mon, Sep 3, 2012 at 1:13 PM, atul anand atul.87fri...@gmail.comwrote: @Dave : algo seems fine...but it seems to me that it would difficult to maintain both left to right and right to left parallel way :( :( . it would be gr8 if you can provided little bit of coded algorithm for it. On Mon, Sep 3, 2012 at 10:36 AM, Dave dave_and_da...@juno.com wrote: @Atul007: No need to destroy the BST. Perform two simultaneous inorder traversals of the BST, one from left to right (the usual direction) and one from right to left. At any stage you have selected two nodes. If the sum is less than the given number, advance the left-to-right traversal; If the sum is greater, advance the right-to-left traversal. Quit with success when the sum equals the given number or with failure when the two traversals have reached the same node. Dave On Sunday, September 2, 2012 11:00:42 PM UTC-5, atul007 wrote: convert BST to sorted DLL.. now it is a double linked list , so we can find 2 number in O(n) time by keeping 2 pointers(one at start and one at end) from sorted DLL. now convert DLL to BST. On Mon, Sep 3, 2012 at 1:32 AM, Navin Kumar algorit...@gmail.comwrote: MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space. -- 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/-/oizd-5CSfuoJ. 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 and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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] maximum length subarray with sum=0
similar discussion is going on in this thread.. reply to this thread ( mentioned below) , if you dont understand the solution. http://groups.google.com/group/algogeeks/browse_thread/thread/74fc4fb182a484eb?hl=en On 9/3/12, Puneet Gautam puneet.nsi...@gmail.com wrote: @atul: i didnt get your algo fully.. Can u just tell me how it works on this array.. {-3 2 1 5 -12 6 1 -2} the aux array would become {-3 -1 0 5 -7 -1 0 -2} then whats the next step.? We analyze the aux for the repeated element which sets subarray start= 2 subarray end=6 then aux contains 0 at two indices 2 and 6.this gives us the correct answer here.. but that wont be the case everytime, right..? everytime start of subarray cant be 0.. Can u clarify more on this..? Coz i dont think it works on every test array.. On Sun, Sep 2, 2012 at 12:32 AM, atul anand atul.87fri...@gmail.com wrote: take aux[] array of same size and store cumulative some at aux[i]=sum{input[0 to i]} now if you find any repeated element at index i and j then, subarray start = i + 1; subarray end = j if array contain 0 at index j then, subarray start = 0; subarray end = j On 9/2/12, Puneet Gautam puneet.nsi...@gmail.com wrote: Given an array of positive and negative integers, we need to find the MAX length subarray having sum as ZERO... Is there a solution less than O(n^2)..? Please help .. i m stuck at this problem.. Thanks Puneet -- 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.
[algogeeks] Re: Can somebody suggest me AO* algo that convert a number n into strigs of 1's
seems no body interested in this.. v bad.. On Sunday, September 2, 2012 11:05:24 PM UTC+5:30, Daemon Dev wrote: Can somebody suggest me AO* algorithm that convert a number n into strigs of 1's n- (n-1)+1; n-ceil(n/2)+floor(n/2) h(n)=n and h(1)=0 Please help.. -- 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/-/vPfdam15wf8J. 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: Can somebody suggest me AO* algo that convert a number n into strigs of 1's
@Daemon: Probably no one understands what you've asked. What does it mean to convert a number n into strigs of 1's? Doesn't that depend on what a strig is and what operations are allowed? E.g., if one of the operations is replacing a digit by the strig 1, the algorithm is pretty simple. Dave On Monday, September 3, 2012 12:20:28 PM UTC-5, Daemon Dev wrote: seems no body interested in this.. v bad.. On Sunday, September 2, 2012 11:05:24 PM UTC+5:30, Daemon Dev wrote: Can somebody suggest me AO* algorithm that convert a number n into strigs of 1's n- (n-1)+1; n-ceil(n/2)+floor(n/2) h(n)=n and h(1)=0 Please help.. -- 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/-/v0gZ1oeAFcQJ. 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] Microsoft written test question
@rahul : Here are the boundary cases need to be taken care of :- suppose given BST is the following :- root=allocate(70); root-right=allocate(75); root-left=allocate(50); root-left-left=allocate(20); root-left-left-right=allocate(25); root-left-left-left=allocate(10); root-left-right=allocate(60); root-left-right-right=allocate(65); root-left-right-left=allocate(55); now suppose node(20) and node(10) get swapped inorder of given tree is :- 20 10 25 50 55 60 65 70 75 now first violation is at node(20) but you wont get second voilation...because rest is in inc order. yes , it can be done by taking care of root of that first violation. On 9/3/12, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @bharat: +1 i have tried some test cases.. working finely.. @anyone pls verify?? On Mon, Sep 3, 2012 at 11:58 AM, bharat b bagana.bharatku...@gmail.comwrote: while doing in-order traversal, we have to check if(prev current) -- then mark prev element for swapping in the first time violation.. if it happens for the second time..then mark current element for swapping. swap both .. If we don't get the violation for the second time .. means both are side-by-side elements .. swap them .. Hope works .. If I miss any case .. correct me thanks, On Sun, Sep 2, 2012 at 7:45 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @navin: can u explain ur algorithms in words pls.. On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar algorithm.i...@gmail.comwrote: void correctBST(struct node *root) { int flag =0; static struct node *temp1, *temp2, *temp3, *prev; static int found; if(found) return; if(root) { correctBST(root-left); if(!temp1 prev root-data prev-data) { temp1 = prev; temp2 = root; swap((temp1-data), (temp2-data)); flag = 1; prev = temp1; } else if(!temp3 prev root-data prev-data) { temp3 = root; swap((temp1-data), (temp2-data)); swap((temp1-data), (temp3-data)); found = 1; return; } if(!flag) prev = root; correctBST(root-right); } } On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: help to solve the following.. Question: Two of the nodes of a BST are swapped. Correct the BST (taken from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd online test 3rd question) -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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 and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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 and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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
Re: [algogeeks] Microsoft written test question
i guess i missed this part of bharat post :- /* If we don't get the violation for the second time .. means both are side-by-side elements .. swap them .. */ i was saying the same.so it will work. On 9/4/12, atul anand atul.87fri...@gmail.com wrote: @rahul : Here are the boundary cases need to be taken care of :- suppose given BST is the following :- root=allocate(70); root-right=allocate(75); root-left=allocate(50); root-left-left=allocate(20); root-left-left-right=allocate(25); root-left-left-left=allocate(10); root-left-right=allocate(60); root-left-right-right=allocate(65); root-left-right-left=allocate(55); now suppose node(20) and node(10) get swapped inorder of given tree is :- 20 10 25 50 55 60 65 70 75 now first violation is at node(20) but you wont get second voilation...because rest is in inc order. yes , it can be done by taking care of root of that first violation. On 9/3/12, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @bharat: +1 i have tried some test cases.. working finely.. @anyone pls verify?? On Mon, Sep 3, 2012 at 11:58 AM, bharat b bagana.bharatku...@gmail.comwrote: while doing in-order traversal, we have to check if(prev current) -- then mark prev element for swapping in the first time violation.. if it happens for the second time..then mark current element for swapping. swap both .. If we don't get the violation for the second time .. means both are side-by-side elements .. swap them .. Hope works .. If I miss any case .. correct me thanks, On Sun, Sep 2, 2012 at 7:45 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @navin: can u explain ur algorithms in words pls.. On Sun, Sep 2, 2012 at 5:53 PM, Navin Kumar algorithm.i...@gmail.comwrote: void correctBST(struct node *root) { int flag =0; static struct node *temp1, *temp2, *temp3, *prev; static int found; if(found) return; if(root) { correctBST(root-left); if(!temp1 prev root-data prev-data) { temp1 = prev; temp2 = root; swap((temp1-data), (temp2-data)); flag = 1; prev = temp1; } else if(!temp3 prev root-data prev-data) { temp3 = root; swap((temp1-data), (temp2-data)); swap((temp1-data), (temp3-data)); found = 1; return; } if(!flag) prev = root; correctBST(root-right); } } On Sun, Sep 2, 2012 at 4:02 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: help to solve the following.. Question: Two of the nodes of a BST are swapped. Correct the BST (taken from GeekforGeeks http://www.geeksforgeeks.org/archives/23272 2nd online test 3rd question) -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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 and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.com -- 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 and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302,