Re: [algogeeks] First k smallest elements
nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth and that soluton can be done in O(N) On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: 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.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] Finding the middle of a singly linked list which has a cycle in it
@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 the.um...@gmail.com 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.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, 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.
Re: [algogeeks] Finding the middle of a singly linked list which has a cycle in it
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 navinmna...@gmail.com 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 the.um...@gmail.com 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.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, 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding the middle of a singly linked list which has a cycle in it
@Umer: I guess the last node in the LL is _not_ pointing to the head back. Rather, its pointing to one of the intermediate nodes. That way, N2 or N2.next might not ever be _head_. See example: 1-2-3-4-5-3, where the last node points to the 3rd node in LL. On Mar 29, 9:21 pm, Umer Farooq the.um...@gmail.com 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 navinmna...@gmail.com 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 the.um...@gmail.com 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.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, 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.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
that will result into an infinite loop, On Mon, Mar 29, 2010 at 9:51 PM, Umer Farooq the.um...@gmail.com 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 navinmna...@gmail.comwrote: @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 the.um...@gmail.com 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.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, 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.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, - Navin Mohan Naidu Great Minds Discuss Ideas Average Minds Discuss Events Small Minds Discuss People -- 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 the.um...@gmail.com 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 navinmna...@gmail.comwrote: @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 the.um...@gmail.com 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.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, 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.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 -- 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.
