On Mon, Dec 20, 2010 at 11:18 AM, Nikhil Agarwal
<[email protected]>wrote:
> 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.In this case its for (x,y,z)=(-1,-1,0) giving a tuple 1
> [max(-2,-1,1)] and so on.
>
> Find minimum of these tuples i.e. 1.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
>
>
>
--
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.
