Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array
@wladimir , its PPT (Pythagoras triplets ) but its number theory based approach http://en.wikipedia.org/wiki/Pythagorean_triple might not be good idea Here is approach : * * *Euclid's formula*[1]http://en.wikipedia.org/wiki/Pythagorean_triple#cite_note-0 is a fundamental formula for generating Pythagorean triples given an arbitrary pair of positive integers *m* and *n* with *m* *n*. The formula states that the integers p=m^2-n^2 , q=2mn r=m^2+n^2 , we have to sort the array in non-increasing order , then for each mn we have to generate the all such p,q,r in worst case it will also requires O(N^2) such p,q,r for each MN isn't it ? then its not less then O(n^2) ?? Even with this approach,The triple generated by Euclid's formula is primitive if and only if *m* and *n* are coprime and *m*-*n* is odd. If both *m* and *n* are odd, then *a*, *b*, and *c* will be even, and so the triple will not be primitive; however, dividing *a*, *b*, and *c* by 2 will yield a primitive triple if *m* and *n* are coprime. @all other , its similar to 3 sun , can't be done in less then O(N^2) if number are not in range , When the integers are in the range [-*u* ... *u*], 3SUM can be solved in time O(n + *u* lg *u*) by representing *S* as a bit vector and performing a discrete convolution using FFT. i wondered if any other algo/code/link you have which works in less then O(N^2) , Better if One Explain The Approach or Algorithm , You Might able to fill Patent :D Thanks Shashank CSE, BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/JQWWHDKMCiAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Please Mention Your Info. Name/Collage/Country and Reason for Joining Algogeek to Minimize Spamming
Hey Guys , to Minimize Spamming Maintaining Quality of Group we Need Support from You. Please Mind Above Message. Happy Learning :) Thanks Team Algogeek -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/HRTpd-Y_MV4J. 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] Amazon Question - Find Pythagorean triplet in an unsorted array
@Shashank ..+1 ..I wud say he must be given a tuning award :D :D for solving such eternal conundrum ;) On Mon, Oct 17, 2011 at 2:37 PM, WgpShashank shashank7andr...@gmail.comwrote: @wladimir , its PPT (Pythagoras triplets ) but its number theory based approach http://en.wikipedia.org/wiki/Pythagorean_triple might not be good idea Here is approach : * * *Euclid's formula*[1]http://en.wikipedia.org/wiki/Pythagorean_triple#cite_note-0 is a fundamental formula for generating Pythagorean triples given an arbitrary pair of positive integers *m* and *n* with *m* *n*. The formula states that the integers p=m^2-n^2 , q=2mn r=m^2+n^2 , we have to sort the array in non-increasing order , then for each mn we have to generate the all such p,q,r in worst case it will also requires O(N^2) such p,q,r for each MN isn't it ? then its not less then O(n^2) ?? Even with this approach,The triple generated by Euclid's formula is primitive if and only if *m* and *n* are coprime and *m*-*n* is odd. If both *m* and *n* are odd, then *a*, *b*, and *c* will be even, and so the triple will not be primitive; however, dividing *a*, *b*, and *c* by 2 will yield a primitive triple if *m* and *n* are coprime. @all other , its similar to 3 sun , can't be done in less then O(N^2) if number are not in range , When the integers are in the range [-*u* ... *u*], 3SUM can be solved in time O(n + *u* lg *u*) by representing *S* as a bit vector and performing a discrete convolution using FFT. i wondered if any other algo/code/link you have which works in less then O(N^2) , Better if One Explain The Approach or Algorithm , You Might able to fill Patent :D Thanks Shashank CSE, BIT Mesra -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/JQWWHDKMCiAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Please Mention Your Info. Name/Collage/Country and Reason for Joining Algogeek to Minimize Spamming
Wee are already members.. What is expected from us.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/vMtV3ewVYSgJ. 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] Please Mention Your Info. Name/Collage/Country and Reason for Joining Algogeek to Minimize Spamming
This is insane!!! You, whatever is your name, are spamming by posting such idiotic things! On Mon, Oct 17, 2011 at 2:47 PM, WgpShashank shashank7andr...@gmail.comwrote: Hey Guys , to Minimize Spamming Maintaining Quality of Group we Need Support from You. Please Mind Above Message. Happy Learning :) Thanks Team Algogeek -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/HRTpd-Y_MV4J. 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] Please Mention Your Info. Name/Collage/Country and Reason for Joining Algogeek to Minimize Spamming
if(you are a member already) No need to post anything, just ignore the post :) On Mon, Oct 17, 2011 at 5:38 PM, sravanreddy001 sravanreddy...@gmail.comwrote: Wee are already members.. What is expected from us.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/vMtV3ewVYSgJ. 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. -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- 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] Please Mention Your Info. Name/Collage/Country and Reason for Joining Algogeek to Minimize Spamming
that was by mistake... ignore the thread :D On Mon, Oct 17, 2011 at 3:51 PM, chirag ahuja sparkle.chi...@gmail.comwrote: This is insane!!! You, whatever is your name, are spamming by posting such idiotic things! On Mon, Oct 17, 2011 at 2:47 PM, WgpShashank shashank7andr...@gmail.comwrote: Hey Guys , to Minimize Spamming Maintaining Quality of Group we Need Support from You. Please Mind Above Message. Happy Learning :) Thanks Team Algogeek -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/HRTpd-Y_MV4J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sorting a array which is already sorted but has some disorder
Insertion sort is pretty good for this. I've seen a case where we were maintaining a list of items sorted by rank. The ranks changed occasionally, but usually only by +/- 5 at the most, in a list of several million. Insertion sort was much faster at putting them back in order compared to quicksort, in this one special case. Don On Oct 16, 11:17 am, sravanreddy001 sravanreddy...@gmail.com wrote: OK.. what is expected? its again sort problem, unless the amount of distortion is constant, in which a Binary search or Insertion sort can be employed to do in O(n) time. Didn't give a programmatic thought. But, if the the amount of distortion is of order n, then sort in O(n lg n) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Code it...
Could be done by a self-modifying program. Don On Oct 15, 5:26 am, kumar raja rajkumar.cs...@gmail.com wrote: you have to write a program which tell about how many times it has run. ex: if you run first time it will print 1. if you run second time it will print 2. like this. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: print vertical sums of a binary tree
I have an alternate method. At every level, maintain records with (x-axis value, nodeValue) and keep them in a queue. After traversal is done, you can sort the elements based on x-Axis value and sum up the nodeValue for records having same x-axis value. But complexity is becoming O(nlogn) because of sorting. On Oct 16, 6:38 pm, sravanreddy001 sravanreddy...@gmail.com wrote: Even I see this as the best solution... O(n) time and space.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Inplace Array Convertion
Great explanation Sunny. But with this approach, won't a single pass suffice? Select a card , find it's new position, insert the card at that position, initialize i to the position of the replaced card repeat till all cards have been processed. The thing we need to remember is whether relative to the new position of the current card, the previous insertion was before or after the newly computed position. Please comment. On Oct 16, 3:36 am, sravanreddy001 sravanreddy...@gmail.com wrote: cheers.. clear explanation. thanks for the effort.. :) so.. we swap 3 elements and.. run for one complete cycle of N/3 time in this prob.. Anika has a recusion of N/3 depth.. may be.. a loop that runs N/3 time should suffice. :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Inplace Array Convertion
I have a hard copy of the book (years back, I implemented a fortran version of the algorithm described in the book). I don't know if you can find an online version or not. I'm sure there is stuff there. Have you done a simple Google search for in place reorder array ?? It's not a difficult algorithm. And Sedgewicks's books are well known. Searches for his name may also yield results. Just FYI: If your rearrangement doesn't have to be in-place... you will achieve more speed by other methods. I did testing with rearrangement of some very large data sets. The in-place method was noticeably slower. It also required you to write your own routine to do the reordering. Using basic fortran, I could do the same thing in just one or two lines of very simple code. The only advantage to the in-place algorithm is that it uses less memory. This should only be important if you are dealing with some very large arrays. Dan :-) On Oct 14, 9:44 pm, Ankur Garg ankurga...@gmail.com wrote: @Dan ..can you post the algo here or link to the book?? @Anika ...yes please post the code here..but please explain a bit about underlying algo ...(algo is more important than actual code ) On Sat, Oct 15, 2011 at 1:54 AM, Dan dant...@aol.com wrote: On Oct 13, 7:52 pm, shiva@Algo shiv.jays...@gmail.com wrote: Convert an array a1 a2 a3...an b1 b2 b3...bn c1 c2 c3...cn to a1b1c1 a2b2c2...anbncn, inplace See the algorithm for memory efficient rearrangement of array elements in one of the books by Robert Sedgewick such as Algorithms in C++ or Algorithms in Pascal, etc. Dan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] K-best assignment problem
Given a cost matrix with N columns and M rows such that M=N, find the K lowest total cost ways to select one item from each column, with the restriction that only one item may be selected from any row. Don -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Inplace Array Convertion
Is the indexing correct ? For eg a1,a2,a3,b1,b2,b3,c1,c2,c3 for a2 the correct position is 3 but acc to the given formula it is 2. On Oct 17, 9:35 pm, Navneet navneetn...@gmail.com wrote: Great explanation Sunny. But with this approach, won't a single pass suffice? Select a card , find it's new position, insert the card at that position, initialize i to the position of the replaced card repeat till all cards have been processed. The thing we need to remember is whether relative to the new position of the current card, the previous insertion was before or after the newly computed position. Please comment. On Oct 16, 3:36 am, sravanreddy001 sravanreddy...@gmail.com wrote: cheers.. clear explanation. thanks for the effort.. :) so.. we swap 3 elements and.. run for one complete cycle of N/3 time in this prob.. Anika has a recusion of N/3 depth.. may be.. a loop that runs N/3 time should suffice. :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Google Interview Question
How was your interview? Can you please share the questions for benefit of others? On Oct 1, 3:37 pm, Siddhartha Banerjee thefourrup...@gmail.com wrote: lol!!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sorting a array which is already sorted but has some disorder
Yes.. And the reason is best case of insertion sort is in the order of n. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/_OJfijjiFVoJ. 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: Sorting a array which is already sorted but has some disorder
But still it will depend on the number of distortions.If the number of distortions are large enuf(=n/2) then its better to resort in the most generic case.Even insertion sort would cost o(n^2) in that case. On Tue, Oct 18, 2011 at 3:57 AM, sravanreddy001 sravanreddy...@gmail.comwrote: Yes.. And the reason is best case of insertion sort is in the order of n. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/_OJfijjiFVoJ. 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. -- Saurabh Singh B.Tech (Computer Science) 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Code it...
@don Do you mean read the source and modify the hard coded value.. This will involve the the compile and linking steps right? Did you mean some thing else? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/FnH0_GX-9gsJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: print vertical sums of a binary tree
I that is what is suggested in the above code. Even here you can avoid the sorting and add all with same x coordinate.. O(n) space as suggested.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/CZ2rgqRAlW0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Reconstruct BST from preorder traversal
How to reconstruct a BST from just the prorder traversal of that tree ? -- 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.
