Re: [algogeeks] BST
i think it can done like this, assume we have to find 'x' and 'y' wer s='x'+'y' 1) select ith node from tree (from beginning to end) 2) y= s - " ith number (node)" 3) now search for 'y' in BST if we found then there is node such that s= x + y; otherwise no.. -- Prashant Kulkarni || Lokaha Samastaha Sukhino Bhavanthu || || Sarve Jana Sukhino Bhavanthu || On Fri, May 14, 2010 at 2:47 AM, divya jain wrote: > form a sorted array from inorder traversal of tree. now take to pointers > one to the beginning of array and other at the end. now check if the sum of > element is greater than reqd sum then increment 1st ptr. if their sum is > less than reqd sum then decrement 2nd ptr. if their sum is equal to the reqd > sum then this is the ans.. > hope it will work.. > > > On 13 May 2010 20:11, jalaj jaiswal wrote: > >> given a bst... find two nodes whose sum is equal to a number k ... in O(n) >> time and constant space... >> >> -- >> With Regards, >> Jalaj Jaiswal >> +919026283397 >> B.TECH IT >> IIIT ALLAHABAD >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Convert a Binary tree into spike.
use BFS traversal method -- Prashant Kulkarni || Lokaha Samastaha Sukhino Bhavanthu || || Sarve Jana Sukhino Bhavanthu || On Wed, May 12, 2010 at 8:48 PM, vinayan c wrote: > Something like this >1 >2 3 > 4 5 67 > > > 1 > | > 2->3 > | > 4->5->6->7 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Finding the middle of a singly linked list which has a cycle in it
@Umer Farooq but cycle can be between the nodes(not like circular list) so we may not get head node. @all i think mukesh answer is right On Mon, Mar 29, 2010 at 9:21 AM, Umer Farooq wrote: > that's why i have a terminating condition. It will keep on iterating until > ((N2 != head)&&(N2->NextPtr != head)) is true. > > head pointer of the linked list will be passed as an argument to the > function. > > > On Mon, Mar 29, 2010 at 7:04 AM, Navin Naidu wrote: > >> @Umer: Its a singly LL and it has cycle. Both N1 and N2 will keep >> traversing within the cycle. >> >> >> >> On Sun, Mar 28, 2010 at 9:56 PM, Umer Farooq wrote: >> >>> I'll appreciate comments on the solution proposed by me. It works the >>> following way: >>> >>> take two pointers, N1 and N2 pointing on the head of the list. >>> >>> Move N2 by two nodes, and N1 by a single node. >>> >>> When N2 reaches head again (or N2->Next is a head) >>> >>> then return N1 which will be pointing to the middle element of the list. >>> >>> Regards >>> Umer Farooq >>> >>> >>> On Sun, Mar 28, 2010 at 2:17 PM, Mukesh Kumar thakur < >>> mukeshraj8...@gmail.com> wrote: >>> hi! in my opinion we can find the middle element in the singly linked which hv the cycle as we know the list doesnt support the concept of cycle coz it has only one direction traversal > but if we take the case when the list hvng the no of element equal > as we hv : n element in the list we hv to find the middle one in genral;simply we divide it in . n/2; or if consider middle elment as a key temp->link=null; temp->first=middle -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> >> >> -- >> Thanks & Regards, >> NMN >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Prashant Kulkarni -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] First k smallest elements
hi, refer cormen book *Medians and Order Statistics* chapter . On Sat, Mar 27, 2010 at 11:14 PM, sharad kumar wrote: > i feel heapify the array to get a min heap and keep extracting root k > times.any further optimisations??? > > > > On Sun, Mar 28, 2010 at 11:33 AM, Priyanka Chatterjee > wrote: > >> Design the most efficient algorithm to find the first k smallest elements >> in an array ? >> >> -- >> Thanks & Regards, >> Priyanka Chatterjee >> Third Year Undergraduate Student, >> Computer Science & Engineering, >> National Institute Of Technology,Durgapur >> India >> http://priyanka-nit.blogspot.com/ >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Prashant Kulkarni NITK -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] parallel algorithm: find majority element
hi u can use Algorithm like CREW (parallel sorting algorithms) On Wed, Dec 9, 2009 at 1:22 PM, sankethm7 <74.san...@gmail.com> wrote: > Hello folks, > does anyone have idea to solve the problem given below: > > Assume that A[1…n] is an array > a. Describe an efficient parallel algorithm that uses n processors to > find the majority element of A >time complexity = O(n) > b. Describe an efficient parallel algorithm that uses p processors, > where p
