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]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
