Hi, I have posted this in stackoverflow. So you may choose to join here as well (this question was asked in an adobe written test)
http://stackoverflow.com/questions/7138874/find-triangular-triplet-in-an-array thanks, Sarvesh On Sun, Aug 21, 2011 at 8:09 PM, sarvesh saran <[email protected]>wrote: > Hi Sanjay > > I think i forgot to mention that in my original post..so sorry about that. > It is a constant array and should not be modified. > > thanks, > Sarvesh > > > > > On Sun, Aug 21, 2011 at 8:08 PM, sarvesh saran <[email protected] > > wrote: > >> Hi Sanjay, >> >> The input is a constant vector. So it cannot be modified. Space >> requirement is O(1) so it cannot be copied. >> >> thanks, >> Sarvesh >> >> >> On Sun, Aug 21, 2011 at 8:04 PM, Sanjay Rajpal <[email protected]> wrote: >> >>> By O(1) we mean that we can use variables, can't use something that >>> equals size of the i/p array. >>> >>> Use Quick sort, sorting is done in-place which O(n log n) in time, and >>> O(1) in space. >>> Sanju >>> :) >>> >>> >>> >>> On Sun, Aug 21, 2011 at 7:31 AM, sarvesh saran < >>> [email protected]> wrote: >>> >>>> Hi Sanjay, >>>> >>>> *Because of O(1) complexity you cannot copy and sort the input array. >>>> >>>> *thanks, >>>> Sarvesh >>>> * >>>> * >>>> >>>> On Sun, Aug 21, 2011 at 8:00 PM, Sanjay Rajpal <[email protected]>wrote: >>>> >>>>> Simply sort the array and check for a[i]+a[i+1] > a[i+2] for i=0 to >>>>> n-3. >>>>> >>>>> >>>>> Sanju >>>>> :) >>>>> >>>>> >>>>> >>>>> On Sun, Aug 21, 2011 at 7:28 AM, sarvesh saran < >>>>> [email protected]> wrote: >>>>> >>>>>> No idea how to solve the problem except the brute force O(n3) >>>>>> approach.I am looking for a better solution than this. Because of O(1) >>>>>> complexity you cannot copy and sort the input. >>>>>> >>>>>> >>>>>> A zero-indexed array A consisting of N integers is given. A triplet >>>>>> (P, Q, R) is triangular if and >>>>>> A[P] + A[Q] > A[R], >>>>>> A[Q] + A[R] > A[P], >>>>>> A[R] + A[P] > A[Q]. >>>>>> >>>>>> For example, consider array A such that >>>>>> >>>>>> A[0] = 10 A[1] = 2 A[2] = 5 >>>>>> A[3] = 1 A[4] = 8 A[5] = 20 >>>>>> Triplet (0, 2, 4) is triangular. >>>>>> >>>>>> public int triangle(int[] A) >>>>>> >>>>>> that, given a zero-indexed array A consisting of N integers, returns 1 >>>>>> if there exists a triangular triplet for this array and returns 0 >>>>>> otherwise. >>>>>> >>>>>> Assume that: >>>>>> >>>>>> N is an integer within the range [0..100,000]; >>>>>> each element of array A is an integer within the >>>>>> range[-2,147,483,648..2,147,483,647]. >>>>>> For example, given array A such that >>>>>> >>>>>> A[0] = 10 A[1] = 2 A[2] = 5 >>>>>> A[3] = 1 A[4] = 8 A[5] = 20 >>>>>> the function should return 1, as explained above. Given arrayA such >>>>>> that >>>>>> >>>>>> A[0] = 10 A[1] = 50 A[2] = 5 >>>>>> A[3] = 1 >>>>>> the function should return 0. >>>>>> Expected worst-case time complexity: O(n log n) >>>>>> Expected worst-case space complexity: O(1) >>>>>> >>>>>> -- >>>>>> You received this message because you are subscribed to the Google >>>>>> Groups "Algorithm Geeks" group. >>>>>> To post to this group, send email to [email protected]. >>>>>> To unsubscribe from this group, send email to >>>>>> [email protected]. >>>>>> 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 [email protected]. >>>>> To unsubscribe from this group, send email to >>>>> [email protected]. >>>>> 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 [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> 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 [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
