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.