BTW can we solve this by hashing..That is the only feasible solution which comes to my mind to reduce the time complexity ?
On Thu, Oct 13, 2011 at 11:20 PM, Ankur Garg <ankurga...@gmail.com> wrote: > Dude this is nothing but 3 sum problem > > http://en.wikipedia.org/wiki/3SUM > > Ask interviewer to check this link and say he has gone mad!! :P > > Regards > Ankur > > On Thu, Oct 13, 2011 at 10:29 PM, ravindra patel <ravindra.it...@gmail.com > > wrote: > >> Hi, >> Another question I faced in Amazon F2F. >> >> Given an unsorted array of integers, find all triplets that satisfy x^2 + >> y^2 = z^2. >> >> For example if given array is - 1, 3, 7, 5, 4, 12, 13 >> The answer should be - >> 5, 12, 13 and >> 3, 4, 5 >> >> I suggested below algo with complexity O(n^2) - >> >> - Sort the array in descending order. - O(nlogn) >> - square each element. - O(n) >> >> Now it reduces to the problem of finding all triplets(a,b,c) in a >> sorted array such that a = b+c. >> >> The interviewer was insisting on a solution better than O(n^2) which I >> dont think is feasible, but I couldn't prove that. Anyone has any idea. >> >> >> >> Thanks, >> - Ravindra >> >> -- >> 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.
