[algogeeks] First k smallest elements
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.
Re: [algogeeks] Finding the middle of the linked list which has also cycle in the list
When the fast pointer points to head again, the slow pointer would point to the middle of the linked list. On Sat, Mar 27, 2010 at 11:51 PM, vikrant singh vikrantsing...@gmail.comwrote: Well gaurav, i think by this method you can only check for a cycle in the list. If u have any idea how can you implement this to solve originally posted problem? On Sat, Mar 27, 2010 at 9:03 AM, gaurav kishan gauravkis...@gmail.comwrote: Hi, Keep two pointers both initially pointing to Head. Move first pointer one by one and the second pointer by two nodes in each iteration. When second pointer next link points to head again,return first pointer. Please let me know if this can be further imporved upon or there is some fallacy in the approach. Regards, Gaurav. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Finding the middle of a singly linked list which has a cycle in it
@black diamond i think u may b wrong. check out this 1-2-3-4-5-6-7-8-9-3-. . . . . . On Sat, Mar 27, 2010 at 11:04 AM, blackDiamond patidarc...@gmail.comwrote: take Two pointers increase one by 1 and other by two node if they match somewhere Firstone will become the middle.. On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.comwrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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
@mukunda , looks like a v nice solution , but can u xplain the step 2 :line2 a bit more clearly? what do u mean by highest length pointer ? Please give an example to your solution. On Sun, Mar 28, 2010 at 9:23 AM, mukunda n s mukundn...@gmail.com wrote: Simplification of the problem would be find the node where the cycle starts then we can easily proceed as we do in singly linked list. 1-2-3-4-5-6-7-8-5 in this case it is 5 let pt1 points to 1(start node) step 1: Find one of nodes inside the cycle.. Proceed in the same way as we go to find whether cycle is there in the linked list or not.. Take 2 pointers increase one pointer ( pt2) by 1 and another pointer(pt3) by 2 when they meet we get a pointer inside the cycle(pt4) of the linked list.. step 2: Find the length(l1) of the list from pt1 to pt4 and then length(l2) of the cycle(pt4 to pt4) . . Now increase the highest length pointer by |l2-l1|..(i.e. if l1 is greater increase it by l1-l2.. l2 is greater increase it by l2-l1..) Now increase both the pointers in the same manner i.e. pt1 and pt4 when they meet we get the point where the cycle starts. step3: Now we know the start pointer and the end pointer...proceed in same manner as the finding the length in the non cyclic linked list.. Efficiency: O(n) On Sat, Mar 27, 2010 at 12:46 PM, saurabh gupta sgup...@gmail.com wrote: Perhaps, if n is the length (from the beginning to the point where the loop ends after a traversal of the loop) then n/2 is the middle, i.e. length of list / 2 in which case middle is easy to find. Is that the definition, Sanjana ? On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.comwrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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 the linked list which has also cycle in the list
vikrant you havent read properly the post by Gaurav when the second pointer will come back to the head first will be pointing the middle.(Think it)!! On Sun, Mar 28, 2010 at 10:21 AM, vikrant singh vikrantsing...@gmail.comwrote: Well gaurav, i think by this method you can only check for a cycle in the list. If u have any idea how can you implement this to solve originally posted problem? On Sat, Mar 27, 2010 at 9:03 AM, gaurav kishan gauravkis...@gmail.comwrote: Hi, Keep two pointers both initially pointing to Head. Move first pointer one by one and the second pointer by two nodes in each iteration. When second pointer next link points to head again,return first pointer. Please let me know if this can be further imporved upon or there is some fallacy in the approach. Regards, Gaurav. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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
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 dona.1...@gmail.comwrote: 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Finding the middle of a singly linked list which has a cycle in it
sorry, i forgot to see *singly* linked list. what about doing a topological sort and returning the middle element. -Rohit On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: @sanjana: but what in case of 1-2-3-1-4-5-6 -Rohit On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.comwrote: For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.comwrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] First k smallest elements
There are about 5-6 solutions mentioned at http://geeksforgeeks.org/forum/topic/kth-largest-element anyone having a different and more efficient algorithm please come up. On Sun, Mar 28, 2010 at 11:44 AM, sharad kumar aryansmit3...@gmail.comwrote: 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 dona.1...@gmail.com 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Junior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.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.
Re: [algogeeks] First k smallest elements
On 28 March 2010 11:44, sharad kumar aryansmit3...@gmail.com wrote: i feel heapify the array to get a min heap and keep extracting root k times.any further optimisations??? This algorithm works in O(n+k logn) time. It is good . Can this be done using randomized selection algorithm in linear time in the worst case? On Sun, Mar 28, 2010 at 11:33 AM, Priyanka Chatterjee dona.1...@gmail.com 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.
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 aryansmit3...@gmail.comwrote: 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 dona.1...@gmail.com 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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] First k smallest elements
select algorithm in order statistics given in cormen book. get kth smallest element in O(n) and output all array elements from index 0 to the index of that kth smallest element. So better than Heap approach which is O(n+klogn) Thanks regards, Laxmikant Agrawal Journey is more important than final goal. On Sun, Mar 28, 2010 at 2:14 AM, sharad kumar aryansmit3...@gmail.comwrote: 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 dona.1...@gmail.com 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Finding the middle of a singly linked list which has a cycle in it
this is impossible case.. how can node1 point to node2 as well as node4?... On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: @sanjana: but what in case of 1-2-3-1-4-5-6 -Rohit On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.comwrote: For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.comwrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Finding the middle of the linked list which has also cycle in the list
@diamond sorry but how do we know the fast pointer is pointing to head again? u see, in case u dont have O(n) space to record visited nodes On Sun, Mar 28, 2010 at 10:28 AM, blackDiamond patidarc...@gmail.comwrote: vikrant you havent read properly the post by Gaurav when the second pointer will come back to the head first will be pointing the middle.(Think it)!! On Sun, Mar 28, 2010 at 10:21 AM, vikrant singh vikrantsing...@gmail.comwrote: Well gaurav, i think by this method you can only check for a cycle in the list. If u have any idea how can you implement this to solve originally posted problem? On Sat, Mar 27, 2010 at 9:03 AM, gaurav kishan gauravkis...@gmail.comwrote: Hi, Keep two pointers both initially pointing to Head. Move first pointer one by one and the second pointer by two nodes in each iteration. When second pointer next link points to head again,return first pointer. Please let me know if this can be further imporved upon or there is some fallacy in the approach. Regards, Gaurav. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Convert a BST into sorted doubly linked list...
How can we convert a BST into a sorted doubly linked list? i have the solution that i traverse BST in inorder traversal and storing elements in doubly linked list. anyone has any best solution. -- Piyush Kumar Verma NIT Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Finding the middle of a singly linked list which has a cycle in it
@Rohit we have a cycle here using hare/tortoise find a node in the cycle find the length of the cycle. find the 'end' of the list, call it E Now equivalent to a singly linked list with the modified termination condition (you need to skip E when you hit it for the first time though) OR find the length of the 'prefix' which touches the cycle, you have the total length, answer = n/2. On Sun, Mar 28, 2010 at 12:43 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: sorry, i forgot to see *singly* linked list. what about doing a topological sort and returning the middle element. -Rohit On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @sanjana: but what in case of 1-2-3-1-4-5-6 -Rohit On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.comwrote: For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.comwrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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 the linked list which has also cycle in the list
in starting we keep track of head pointer.. we are having three pointers head,slower,faster, know we start traversing the list if(faster==head||faster-next==head) return slower else faster=faster-next-next slower=slower-next On Sun, Mar 28, 2010 at 12:15 PM, vikrant singh vikrantsing...@gmail.comwrote: @diamond sorry but how do we know the fast pointer is pointing to head again? u see, in case u dont have O(n) space to record visited nodes On Sun, Mar 28, 2010 at 10:28 AM, blackDiamond patidarc...@gmail.comwrote: vikrant you havent read properly the post by Gaurav when the second pointer will come back to the head first will be pointing the middle.(Think it)!! On Sun, Mar 28, 2010 at 10:21 AM, vikrant singh vikrantsing...@gmail.com wrote: Well gaurav, i think by this method you can only check for a cycle in the list. If u have any idea how can you implement this to solve originally posted problem? On Sat, Mar 27, 2010 at 9:03 AM, gaurav kishan gauravkis...@gmail.comwrote: Hi, Keep two pointers both initially pointing to Head. Move first pointer one by one and the second pointer by two nodes in each iteration. When second pointer next link points to head again,return first pointer. Please let me know if this can be further imporved upon or there is some fallacy in the approach. Regards, Gaurav. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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
@Rohit we have a cycle here On Sun, Mar 28, 2010 at 2:42 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: that is topologcall sort On 3/28/10, saurabh gupta sgup...@gmail.com wrote: @Rohit we have a cycle here using hare/tortoise find a node in the cycle find the length of the cycle. find the 'end' of the list, call it E Now equivalent to a singly linked list with the modified termination condition (you need to skip E when you hit it for the first time though) OR find the length of the 'prefix' which touches the cycle, you have the total length, answer = n/2. On Sun, Mar 28, 2010 at 12:43 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: sorry, i forgot to see singly linked list. what about doing a topological sort and returning the middle element. -Rohit On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @sanjana: but what in case of 1-2-3-1-4-5-6 -Rohit On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.com wrote: For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.com wrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Rohit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears.
Re: [algogeeks] Finding the middle of a singly linked list which has a cycle in it
sry... i got confused -Rohit On Sun, Mar 28, 2010 at 3:14 PM, saurabh gupta sgup...@gmail.com wrote: @Rohit we have a cycle here On Sun, Mar 28, 2010 at 2:42 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: that is topologcall sort On 3/28/10, saurabh gupta sgup...@gmail.com wrote: @Rohit we have a cycle here using hare/tortoise find a node in the cycle find the length of the cycle. find the 'end' of the list, call it E Now equivalent to a singly linked list with the modified termination condition (you need to skip E when you hit it for the first time though) OR find the length of the 'prefix' which touches the cycle, you have the total length, answer = n/2. On Sun, Mar 28, 2010 at 12:43 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: sorry, i forgot to see singly linked list. what about doing a topological sort and returning the middle element. -Rohit On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @sanjana: but what in case of 1-2-3-1-4-5-6 -Rohit On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.com wrote: For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.com wrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Rohit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is
Re: [algogeeks] Finding the middle of a singly linked list which has a cycle in it
anyways.. the solution becomes still more trivial... as there can be only one cycle remove it easily and that helps to find the centre. -Rohit On Sun, Mar 28, 2010 at 4:12 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: sry... i got confused -Rohit On Sun, Mar 28, 2010 at 3:14 PM, saurabh gupta sgup...@gmail.com wrote: @Rohit we have a cycle here On Sun, Mar 28, 2010 at 2:42 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: that is topologcall sort On 3/28/10, saurabh gupta sgup...@gmail.com wrote: @Rohit we have a cycle here using hare/tortoise find a node in the cycle find the length of the cycle. find the 'end' of the list, call it E Now equivalent to a singly linked list with the modified termination condition (you need to skip E when you hit it for the first time though) OR find the length of the 'prefix' which touches the cycle, you have the total length, answer = n/2. On Sun, Mar 28, 2010 at 12:43 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: sorry, i forgot to see singly linked list. what about doing a topological sort and returning the middle element. -Rohit On Sun, Mar 28, 2010 at 11:54 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @sanjana: but what in case of 1-2-3-1-4-5-6 -Rohit On Sat, Mar 27, 2010 at 11:19 PM, Sanjana - sanjana.2...@gmail.com wrote: For ex if there is 1-2-3-4-5-6-7-8-5 then no. of unique nodes is 8 then the loop keeps on repeating. So the middle is 4 or 5 On Sat, Mar 27, 2010 at 11:01 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: how do u define middle when there is a cycle in the list ? -Rohit On Sat, Mar 27, 2010 at 12:11 AM, Sanjana sanjana.2...@gmail.com wrote: Hello, Can someone help me out with this. How to find the middle of a singly linked list which also has a cycle in it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Rohit -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at
Re: [algogeeks] Convert a BST into sorted doubly linked list...
This is the best description. http://cslibrary.stanford.edu/109/TreeListRecursion.html Thanks Pramod Negi On Sun, Mar 28, 2010 at 1:39 PM, Piyush Verma 114piy...@gmail.com wrote: How can we convert a BST into a sorted doubly linked list? i have the solution that i traverse BST in inorder traversal and storing elements in doubly linked list. anyone has any best solution. -- Piyush Kumar Verma NIT 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] First k smallest elements
Create a temp array temp[0..k-1] of size k. 2) Traverse the array arr[k..n-1]. While traversing, keep updating the smallest element of temp[] 3) Return the smallest of temp[] Time Complexity: O((n-k)*k). try it ..for this problem[?] -- 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. 338.gif
Re: [algogeeks] Finding the middle of the linked list which has also cycle in the list
if(faster==head||faster-next=
=head)
return slower
else
faster=faster-next-next
slower=slower-next
HERE we hv three poniter faster,headr,slower.
as u hv mentioned that linked list has cycle list so better is that we hv
to use for loop
as :-
if we take headr,link,temp;
if(temp==headr)
{
link-temp=first;
}
else
return temp;
for(temp-first=null;tempheadr;temp-link++)
{
we can print the middle element;
}
or inplace of this we can use the pointer concept to assign the middle and
faster element..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] how to convert a BST into a sorted doubly linked list.
how to convert a BST into a sorted doubly linked list. is there any solution of this question. -- 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 BST into sorted doubly linked list...
Here it is a nice solution: http://cslibrary.stanford.edu/109/TreeListRecursion.html On Sun, Mar 28, 2010 at 11:09 AM, Piyush Verma 114piy...@gmail.com wrote: How can we convert a BST into a sorted doubly linked list? i have the solution that i traverse BST in inorder traversal and storing elements in doubly linked list. anyone has any best solution. -- Piyush Kumar Verma NIT 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] First k smallest elements
you have to find the kth element of your list. which will take O(n) and remaining element you can get in the other traversal eg: 3,5,4,35,599,34 you have to find the 3 min element from the lsit so finding 3rd element we will get 5 on next thing is traverse the list and take all the element less than 5, eg:3,5,4 is this clear your doubt ...? or i have gone on the other way... On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy abhijith200...@gmail.comwrote: Can any one tell how to do this when there are 'm' queries like query i j k find the kth largest element in between indices i-j in an array. When m is large even an O(n) algorithm would be slow. I thinking that each query could be answered in O(sqrt(n)) time So any suggestions ? Thanks On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond patidarc...@gmail.comwrote: there are better solution of O(n) are posted in the thread...[?]. using order statices On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: Create a temp array temp[0..k-1] of size k. 2) Traverse the array arr[k..n-1]. While traversing, keep updating the smallest element of temp[] 3) Return the smallest of temp[] Time Complexity: O((n-k)*k). try it ..for this problem[?] -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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. 338.gif361.gif
Re: [algogeeks] First k smallest elements
1) Construct max heap by taking first k elements in an array 2) if k+1 element less than root of max heap a) Delete root of max heap b) Insert k+1 element in max heap and apply heapify method 3) else skip the element 4) apply above procedure for all n elements in an array At last you will get k smallest elements and root is kth smallest element in the array this is O(nlogk) CHERUVU JAANU REDDY M.Tech in CSIS On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy abhijith200...@gmail.comwrote: Can any one tell how to do this when there are 'm' queries like query i j k find the kth largest element in between indices i-j in an array. When m is large even an O(n) algorithm would be slow. I thinking that each query could be answered in O(sqrt(n)) time So any suggestions ? Thanks On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond patidarc...@gmail.comwrote: there are better solution of O(n) are posted in the thread...[?]. using order statices On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: Create a temp array temp[0..k-1] of size k. 2) Traverse the array arr[k..n-1]. While traversing, keep updating the smallest element of temp[] 3) Return the smallest of temp[] Time Complexity: O((n-k)*k). try it ..for this problem[?] -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. 338.gif361.gif
Re: [algogeeks] how to convert a BST into a sorted doubly linked list.
insert the elements in the list, the elements of the tree visited by inorder traversal On Sun, Mar 28, 2010 at 11:13 AM, Piyush Verma 114piy...@gmail.com wrote: how to convert a BST into a sorted doubly linked list. is there any solution of this question. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
