Re: [algogeeks] Re: DS Q
On Thu, Nov 17, 2011 at 4:05 PM, shady sinv...@gmail.com wrote: you can't do binary search with linked lists. Yes you can do the binary search on the linked list. But the only difference it makes from the array is that array elements can be accessed in O(1) time and finding the mid in array is O(1) where it is not possible with (1) on linked list. Yes you can find mid but that will be expensive than array. On Nov 17, 1:14 pm, Vijay Khandar vijaykhand...@gmail.com wrote: Linked lists are not suitable data structures of which one of the following problems? a) Insertion sort b) Binary search c) Radix sort d) Polynomial manipulation Plz explain anyone in detail Vijay... -- 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, Sumit Mahamuni. -- Slow code that scales better can be faster than fast code that doesn't scale! -- Tough times never lasts, but tough people do. -- I love deadlines. I like the whooshing sound they make as they fly by. - D. Adams -- 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: DS Q
roflmao, that's what i mean, else the whole purpose of binary search is defeated, instead just linearly traverse the array and find the element On Thu, Nov 17, 2011 at 4:17 PM, sumit mahamuni sumit143smail...@gmail.comwrote: On Thu, Nov 17, 2011 at 4:05 PM, shady sinv...@gmail.com wrote: you can't do binary search with linked lists. Yes you can do the binary search on the linked list. But the only difference it makes from the array is that array elements can be accessed in O(1) time and finding the mid in array is O(1) where it is not possible with (1) on linked list. Yes you can find mid but that will be expensive than array. On Nov 17, 1:14 pm, Vijay Khandar vijaykhand...@gmail.com wrote: Linked lists are not suitable data structures of which one of the following problems? a) Insertion sort b) Binary search c) Radix sort d) Polynomial manipulation Plz explain anyone in detail Vijay... -- 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, Sumit Mahamuni. -- Slow code that scales better can be faster than fast code that doesn't scale! -- Tough times never lasts, but tough people do. -- I love deadlines. I like the whooshing sound they make as they fly by. - D. Adams -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: ds
Hello All, What every algorithm mentioned above have some problem. The Recursive swapping won’t work if you don’t have 2^n elements. Same with getting the indexes, it will form a cycle. Thanks Pramod Negi On Fri, Jun 11, 2010 at 7:09 PM, sharad kumar sharad20073...@gmail.comwrote: excellent soln!! -- 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] Re: ds
excellent soln!! -- 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] Re: ds
nice algo! Anurag Sharma On Wed, Jun 9, 2010 at 11:23 PM, souravsain souravs...@gmail.com wrote: Guys We can solve this in O(n) time like this: Let me say total elements in array is 2N such that 1 to N are a's and N +1 to 2N (which I will again refer to as 1 to N) are b's Observation: If an element is on first 1 to N (an 'a') and has index i then in the final array its position index (in the final 2N array) will be i+(i-1) [current index + no. of positions lying to the left]. If an element is on the second 1 to N (the b's series) and has index j then in the final array of 2N, its index will be 2j. With this observation we start with the last element of first series, the a's and find its final position in result array. Place the element in final position. Take the element which is lying there and find this elements new position and go on. Example: start with temp=a6 (the last element of furst series) a1,a2,a3,a4,a5,a6,b1,b2,b3,b4,b5,b6 temp=a6, final position of a6 = 6+(6-1) = 11. Put a6 in eleventh position and take the element at 11th position into temp: So now a1,a2,a3,a4,a5,a6,b1,b2,b3,b4,a6,b6 and temp = b5. Final position of b5 = 2*5 = 10. Put b5 at 10th position and take previous element in temp. So now a1,a2,a3,a4,a5,a6,b1,b2,b3,b5,a6,b6 and temp = b4. Final position of b4 = 2*4 = 8. Put b4 at 8th position and take previous element at 8th in temp. So now a1,a2,a3,a4,a5,a6,b1,b4,b3,b5,a6,b6 and temp = b2, going this way we will have next position of b2 = 2*2=4 a1,a2,a3,b2,a5,a6,b1,b4,b3,b5,a6,b6 and temp = a4: next position of a4 = 4 + (4-1) = 7 a1,a2,a3,b2,a5,a6,b4,b4,b3,b5,a6,b6 and temp=b1: next position of b1 = 1*2=2 a1,b1,a3,b2,a5,a6,b4,b4,b3,b5,a6,b6 and temp=a2:next position of a2 = 2+(2-1)=3 a1,b1,a2,b2,a5,a6,b4,b4,b3,b5,a6,b6 and temp=a3:next position of a3 = 3+(3-1)=5 a1,b1,a2,b2,a3,a6,b4,b4,b3,b5,a6,b6 and temp=a5:next position of a5 = 5+(5-1)=9 a1,b1,a2,b2,a3,a6,b4,b4,a5,b5,a6,b6 and temp=b3:next position of b3 = 3*2=6 a1,b1,a2,b2,a3,b3,b4,b4,a5,b5,a6,b6 and temp=a6:next position of a6 = 6 + (6-1)=11 But now we find a6 already present at 11. Hence arranged in O(n) time and constant space of 1 temp variable Thanks, Sourav Sain On Jun 9, 8:54 pm, Anurag Sharma anuragvic...@gmail.com wrote: Its not O(n) time. Anurag Sharma On Wed, Jun 9, 2010 at 5:46 PM, Jitendra Kushwaha jitendra.th...@gmail.comwrote: here is a sel explainatory algo given: abcd1234 abc1d234 ab1c2d34 a1b2c3d4 here is the link for the code :http://codepad.org/SZnufGc6 -- Regards Jitendra Kushwaha MNNIT, 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 algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- 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] Re: ds
here is a sel explainatory algo given: abcd1234 abc1d234 ab1c2d34 a1b2c3d4 here is the link for the code : http://codepad.org/SZnufGc6 -- Regards Jitendra Kushwaha MNNIT, 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] Re: ds
Its not O(n) time. Anurag Sharma On Wed, Jun 9, 2010 at 5:46 PM, Jitendra Kushwaha jitendra.th...@gmail.comwrote: here is a sel explainatory algo given: abcd1234 abc1d234 ab1c2d34 a1b2c3d4 here is the link for the code : http://codepad.org/SZnufGc6 -- Regards Jitendra Kushwaha MNNIT, 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] Re: ds
which is just the recursive version of the abovementioned iterative solution. P.S. -Please remove this quoted text when you are composing -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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.