I have a solution.I cant prove the correctness but by intuition I can
conclude.This is O(1) solution.
As we have 3 sorted arrays A,B,C.So only first and last element of these 3
lists will be contributing for min/max tuple.Rest elements will be varying
from that max to min.
Suppose a={-1,-1,0}
b={-1,3,7,8,10}
c={0,1,2,3,4,5}
so -1,0 of A ,-1,10 of B and 0,5 of C will be contributing .So we find all
possible 8 tuples.Find minimum of these tuples.That will be the
answer.Solution if O(8) equilvalent to O(1).Please provide counter if you
can find.
On Mon, Dec 20, 2010 at 10:54 AM, yq Zhang <[email protected]> wrote:
> This question is equivalent to finding the minimum window contains 3 words
> in a document given the position of appearance of each word in the document
> by array A, B, C. This could be solved by a typical sliding window algorithm
> which is O(n).
>
> Thanks
>
>
>
>
>
>
> On Sun, Dec 19, 2010 at 9:06 PM, Saurabh Koar <[email protected]>wrote:
>
>> @yq: Plz explain your algorithm.
>>
>> On 12/20/10, yq Zhang <[email protected]> wrote:
>> > Are A, B, C sorted? If so, I believe there is a O(n1+n2+n3) solution for
>> > this question.
>> >
>> > Thanks
>> >
>> >
>> > On Sun, Dec 19, 2010 at 9:57 AM, Saurabh Koar
>> > <[email protected]>wrote:
>> >
>> >> You are given 3 integer arrays A, B and C of length n1, n2 and n3
>> >> respectively. All arrays are sorted. We define triplet of these 3
>> >> arrays as (x,y,z) where x is any integer from A, y from B and z from
>> >> C. We define distance of triplet as maximum difference among triplet
>> >> elements, i.e. Maximum of x – y, y – z or z – x. Write a program to
>> >> find minimum triplet distance. (means there are n1*n2*n3 number of
>> >> possible triplets are possible...among all triplets which triplet has
>> >> minimum distance...Give only distance, but not triplet elements). Your
>> >> program must be as much efficient as possible.
>> >>
>> >> --
>> >> 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]<algogeeks%[email protected]>
>> <algogeeks%[email protected]<algogeeks%[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]<algogeeks%[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]<algogeeks%[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]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Thanks & Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science & Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
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.
