Re: [algogeeks] Re: Intersection of arrays

[Anup Ghatage]

Here is another idea if space is available

Step 1: Go through the whole array, find the maximum. Create a hash table of
the maximum value.
Step 2: Hash the arrays, one by one and re-create them with only unique
elements. (discard on collision)
Step 3: Once you get the unique arrays, create another hash table, but this
time, use the same table for all three arrays.
  Hash all entries with a count variable, which gets incremented
on a collision.
Step 4: Traverse the Hash table, display all entries whose count == K

Those are your intersections.

On Fri, Oct 28, 2011 at 8:43 PM, Dumanshu  wrote:

> I think Dan's solution is the best one here. TC O(n log n) and SC O(1)
> where n is the maximum no. of elements in any array
> Instead of starting with K given arrays, just take the first 2.
> Sort both of them - time is nlogn
> Now run two pointers on each array to save the common elements as they
> are and clear the rest in 1st array. Discard 2nd array now.
> We have 1st array with intersection elements only.
> Now continue the same thing - With 1st array and 3rd array. Sort 3rd
> array. Keep common elements in 1st array and clear the rest.
>
> Keeping common elements in 2 arrays and clearing the other elements
> can be done in O(n) TC.
>
> On Oct 25, 11:17 am, kumar raja  wrote:
> >  Find intersection of K unsorted array of N elements each. Intersection
> > consists of elements that appear in all the K arrays.
> >
> > what data structure is useful here??
> >
> > --
> > Regards
> > Kumar Raja
> > M.Tech(SIT)
> > IIT Kharagpur,
> > 10it60...@iitkgp.ac.in
>
> --
> 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.
>
>


-- 
Anup Ghatage

-- 
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.

[algogeeks] Re: Intersection of arrays

[Dumanshu]

I think Dan's solution is the best one here. TC O(n log n) and SC O(1)
where n is the maximum no. of elements in any array
Instead of starting with K given arrays, just take the first 2.
Sort both of them - time is nlogn
Now run two pointers on each array to save the common elements as they
are and clear the rest in 1st array. Discard 2nd array now.
We have 1st array with intersection elements only.
Now continue the same thing - With 1st array and 3rd array. Sort 3rd
array. Keep common elements in 1st array and clear the rest.

Keeping common elements in 2 arrays and clearing the other elements
can be done in O(n) TC.

On Oct 25, 11:17 am, kumar raja  wrote:
>  Find intersection of K unsorted array of N elements each. Intersection
> consists of elements that appear in all the K arrays.
>
> what data structure is useful here??
>
> --
> Regards
> Kumar Raja
> M.Tech(SIT)
> IIT Kharagpur,
> 10it60...@iitkgp.ac.in

-- 
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.

[algogeeks] Re: Intersection of arrays

[icy`]

you didnt mention if duplicate elements should appear in the
intersection or not.  If no duplicates necessary, then your language
may already have intersection between arrays built in.  Or you should
write an intersection operator/method between arrays  (in ruby it is
just the "&"  operator).   My example output:

arrays: 6
elements in each array: 20
range: 1 to 5
array #1: [4, 5, 5, 1, 4, 3, 4, 3, 2, 5, 2, 5, 1, 3, 3, 1, 2, 3, 1, 5]
array #2: [2, 2, 3, 5, 2, 5, 1, 1, 2, 3, 1, 1, 2, 5, 3, 2, 3, 3, 2, 2]
array #3: [1, 3, 2, 5, 4, 3, 1, 1, 2, 1, 5, 4, 4, 4, 2, 2, 5, 1, 2, 2]
array #4: [3, 5, 4, 5, 1, 2, 3, 4, 3, 2, 1, 1, 2, 2, 4, 1, 2, 3, 2, 3]
array #5: [2, 1, 5, 2, 1, 4, 3, 2, 3, 1, 2, 4, 4, 2, 4, 5, 5, 3, 5, 5]
array #6: [4, 4, 2, 5, 3, 2, 5, 3, 5, 3, 2, 4, 4, 2, 5, 5, 4, 3, 1, 1]
intersection: [2, 1, 3]

my intersection here is simply  ar1 & ar2 & ar3 & ar4 & ar5 & ar6  ,
no duplicates show up.

On Oct 28, 3:09 am, kumar raja  wrote:
> How is it possible to create a hash map using elements as keys and their
> counts as values .If we give some key the value is automatically computed by
> hash function .If u are given an element/key its index/value is calculated
> by hash function.am i corrct??
>
> On 27 October 2011 22:36, Nitin Garg  wrote:
>
>
>
>
>
>
>
>
>
> > The hashing solution is similar to the 1st answer 
> > here
>
> > A sorting solution will take O(k.n.logn)  time
>
> > On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage  wrote:
>
> >> Don,
> >> As you said, the intersection set, won't really be in sorted order as it
> >> depends on the elements of the second array, which are unsorted. Still,
> >> sorting them wouldn't be much different as it'd be worst case O(n logn).. [
> >> Array 2 == Array 1 ]
> >> But sorting the First Array has already cost O(n logn)
>
> >> So I guess the worse case complexity has to be O(n logn) anyway..
>
> >> On Thu, Oct 27, 2011 at 10:54 PM, Dan  wrote:
>
> >>> Hashing all of the K arrays seems like a bit much.   How about this?
>
> >>> You have  K  seperate arrays to start with,  each array having N
> >>> elements (is that correct?).
>
> >>> 1)  Sort the first array.
>
> >>> 2)  Step through the 2nd array, 1 element at a time  say
> >>> Array(2).element(i)
> >>>     Check to see if the value of  Array(2).element(i) is in the first
> >>> sorted array.
> >>>     If it is,  add this numeric value to your list of  "intersection
> >>> elements".
>
> >>>     As you pass through all elements of the 2nd array,  the values
> >>> found which
> >>>     are intersecting need to be saved  ( maybe in the 1st arrays
> >>> space to save
> >>>      memory).   Ideally, these should be saved in sorted order as
> >>> they are found.
>
> >>>     ( how you store the sorted array will affect speed of this check
> >>> of course.
> >>>       I'd keep it simple on the 1st round, then optimize the code
> >>> once everything
> >>>       appears to be working well, ie with buckets or pointers or
> >>> whatever.  How
> >>>       you determine if an element in array 2 intersects with an
> >>> element of array
> >>>       1 will depend on how you store your sorted array.  You might do
> >>> a linear
> >>>       search or a binary search or a bucket search of some sort ).
>
> >>> 3)  Now...  step through the 3rd array,  1 element at a time,  looking
> >>> to see if each
> >>>    value is in the  just created  list  of   "intersection elements"
>
> >>> 4)  Do the save thing now with each of the remaining original K
> >>> arrays.
>
> >>> Dan    :-)
>
> >>> On Oct 24, 10:17 pm, kumar raja  wrote:
> >>> >  Find intersection of K unsorted array of N elements each. Intersection
> >>> > consists of elements that appear in all the K arrays.
>
> >>> > what data structure is useful here??
>
> >>> > --
> >>> > Regards
> >>> > Kumar Raja
> >>> > M.Tech(SIT)
> >>> > IIT Kharagpur,
> >>> > 10it60...@iitkgp.ac.in
>
> >>> --
> >>> 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.
>
> >> --
> >> Anup Ghatage
>
> >>  --
> >> 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.
>
> > --
> > Nitin Garg
>
> > "Personality can open doors, but only Character can keep them open"
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to

[algogeeks] Re: Intersection of arrays

[icy`]

sorry, i made a slight coding mistake in my last post (invisible 7th
array) , but the logic remains the same...corrected sample output:

arrays: 6
elements in each array: 20
range: 1 to 5
array #1: [3, 4, 3, 4, 5, 3, 2, 2, 1, 4, 2, 3, 4, 4, 3, 1, 3, 2, 4, 4]
array #2: [1, 4, 5, 2, 1, 5, 1, 4, 3, 1, 3, 2, 5, 4, 4, 1, 3, 4, 5, 3]
array #3: [4, 3, 4, 3, 3, 5, 2, 5, 4, 5, 2, 2, 1, 5, 5, 4, 4, 1, 2, 2]
array #4: [4, 2, 5, 1, 1, 1, 1, 1, 5, 5, 1, 3, 4, 1, 5, 4, 3, 5, 2, 5]
array #5: [3, 4, 2, 5, 1, 4, 1, 5, 5, 5, 3, 5, 2, 1, 4, 1, 1, 5, 2, 5]
array #6: [5, 5, 2, 4, 3, 5, 5, 4, 1, 4, 2, 3, 1, 1, 5, 2, 5, 1, 3, 4]
intersection: [3, 4, 5, 2, 1]


On Oct 28, 3:09 am, kumar raja  wrote:
> How is it possible to create a hash map using elements as keys and their
> counts as values .If we give some key the value is automatically computed by
> hash function .If u are given an element/key its index/value is calculated
> by hash function.am i corrct??
>
> On 27 October 2011 22:36, Nitin Garg  wrote:
>
>
>
>
>
>
>
>
>
> > The hashing solution is similar to the 1st answer 
> > here
>
> > A sorting solution will take O(k.n.logn)  time
>
> > On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage  wrote:
>
> >> Don,
> >> As you said, the intersection set, won't really be in sorted order as it
> >> depends on the elements of the second array, which are unsorted. Still,
> >> sorting them wouldn't be much different as it'd be worst case O(n logn).. [
> >> Array 2 == Array 1 ]
> >> But sorting the First Array has already cost O(n logn)
>
> >> So I guess the worse case complexity has to be O(n logn) anyway..
>
> >> On Thu, Oct 27, 2011 at 10:54 PM, Dan  wrote:
>
> >>> Hashing all of the K arrays seems like a bit much.   How about this?
>
> >>> You have  K  seperate arrays to start with,  each array having N
> >>> elements (is that correct?).
>
> >>> 1)  Sort the first array.
>
> >>> 2)  Step through the 2nd array, 1 element at a time  say
> >>> Array(2).element(i)
> >>>     Check to see if the value of  Array(2).element(i) is in the first
> >>> sorted array.
> >>>     If it is,  add this numeric value to your list of  "intersection
> >>> elements".
>
> >>>     As you pass through all elements of the 2nd array,  the values
> >>> found which
> >>>     are intersecting need to be saved  ( maybe in the 1st arrays
> >>> space to save
> >>>      memory).   Ideally, these should be saved in sorted order as
> >>> they are found.
>
> >>>     ( how you store the sorted array will affect speed of this check
> >>> of course.
> >>>       I'd keep it simple on the 1st round, then optimize the code
> >>> once everything
> >>>       appears to be working well, ie with buckets or pointers or
> >>> whatever.  How
> >>>       you determine if an element in array 2 intersects with an
> >>> element of array
> >>>       1 will depend on how you store your sorted array.  You might do
> >>> a linear
> >>>       search or a binary search or a bucket search of some sort ).
>
> >>> 3)  Now...  step through the 3rd array,  1 element at a time,  looking
> >>> to see if each
> >>>    value is in the  just created  list  of   "intersection elements"
>
> >>> 4)  Do the save thing now with each of the remaining original K
> >>> arrays.
>
> >>> Dan    :-)
>
> >>> On Oct 24, 10:17 pm, kumar raja  wrote:
> >>> >  Find intersection of K unsorted array of N elements each. Intersection
> >>> > consists of elements that appear in all the K arrays.
>
> >>> > what data structure is useful here??
>
> >>> > --
> >>> > Regards
> >>> > Kumar Raja
> >>> > M.Tech(SIT)
> >>> > IIT Kharagpur,
> >>> > 10it60...@iitkgp.ac.in
>
> >>> --
> >>> 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.
>
> >> --
> >> Anup Ghatage
>
> >>  --
> >> 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.
>
> > --
> > Nitin Garg
>
> > "Personality can open doors, but only Character can keep them open"
>
> > --
> > 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.
>
> --
> Regards
> Kumar Raja
> M.Tech(SIT)
> IIT

Re: [algogeeks] Re: Intersection of arrays

[kumar raja]

How is it possible to create a hash map using elements as keys and their
counts as values .If we give some key the value is automatically computed by
hash function .If u are given an element/key its index/value is calculated
by hash function.am i corrct??

On 27 October 2011 22:36, Nitin Garg  wrote:

> The hashing solution is similar to the 1st answer 
> here
>
> A sorting solution will take O(k.n.logn)  time
>
>
>
> On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage  wrote:
>
>> Don,
>> As you said, the intersection set, won't really be in sorted order as it
>> depends on the elements of the second array, which are unsorted. Still,
>> sorting them wouldn't be much different as it'd be worst case O(n logn).. [
>> Array 2 == Array 1 ]
>> But sorting the First Array has already cost O(n logn)
>>
>> So I guess the worse case complexity has to be O(n logn) anyway..
>>
>>
>> On Thu, Oct 27, 2011 at 10:54 PM, Dan  wrote:
>>
>>> Hashing all of the K arrays seems like a bit much.   How about this?
>>>
>>> You have  K  seperate arrays to start with,  each array having N
>>> elements (is that correct?).
>>>
>>> 1)  Sort the first array.
>>>
>>> 2)  Step through the 2nd array, 1 element at a time  say
>>> Array(2).element(i)
>>> Check to see if the value of  Array(2).element(i) is in the first
>>> sorted array.
>>> If it is,  add this numeric value to your list of  "intersection
>>> elements".
>>>
>>> As you pass through all elements of the 2nd array,  the values
>>> found which
>>> are intersecting need to be saved  ( maybe in the 1st arrays
>>> space to save
>>>  memory).   Ideally, these should be saved in sorted order as
>>> they are found.
>>>
>>> ( how you store the sorted array will affect speed of this check
>>> of course.
>>>   I'd keep it simple on the 1st round, then optimize the code
>>> once everything
>>>   appears to be working well, ie with buckets or pointers or
>>> whatever.  How
>>>   you determine if an element in array 2 intersects with an
>>> element of array
>>>   1 will depend on how you store your sorted array.  You might do
>>> a linear
>>>   search or a binary search or a bucket search of some sort ).
>>>
>>> 3)  Now...  step through the 3rd array,  1 element at a time,  looking
>>> to see if each
>>>value is in the  just created  list  of   "intersection elements"
>>>
>>> 4)  Do the save thing now with each of the remaining original K
>>> arrays.
>>>
>>> Dan:-)
>>>
>>>
>>>
>>> On Oct 24, 10:17 pm, kumar raja  wrote:
>>> >  Find intersection of K unsorted array of N elements each. Intersection
>>> > consists of elements that appear in all the K arrays.
>>> >
>>> > what data structure is useful here??
>>> >
>>> > --
>>> > Regards
>>> > Kumar Raja
>>> > M.Tech(SIT)
>>> > IIT Kharagpur,
>>> > 10it60...@iitkgp.ac.in
>>>
>>> --
>>> 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.
>>>
>>>
>>
>>
>> --
>> Anup Ghatage
>>
>>  --
>> 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.
>>
>
>
>
> --
> Nitin Garg
>
> "Personality can open doors, but only Character can keep them open"
>
> --
> 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.
>



-- 
Regards
Kumar Raja
M.Tech(SIT)
IIT Kharagpur,
10it60...@iitkgp.ac.in

-- 
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.

Re: [algogeeks] Re: Intersection of arrays

[Nitin Garg]

The hashing solution is similar to the 1st answer
here

A sorting solution will take O(k.n.logn)  time



On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage  wrote:

> Don,
> As you said, the intersection set, won't really be in sorted order as it
> depends on the elements of the second array, which are unsorted. Still,
> sorting them wouldn't be much different as it'd be worst case O(n logn).. [
> Array 2 == Array 1 ]
> But sorting the First Array has already cost O(n logn)
>
> So I guess the worse case complexity has to be O(n logn) anyway..
>
>
> On Thu, Oct 27, 2011 at 10:54 PM, Dan  wrote:
>
>> Hashing all of the K arrays seems like a bit much.   How about this?
>>
>> You have  K  seperate arrays to start with,  each array having N
>> elements (is that correct?).
>>
>> 1)  Sort the first array.
>>
>> 2)  Step through the 2nd array, 1 element at a time  say
>> Array(2).element(i)
>> Check to see if the value of  Array(2).element(i) is in the first
>> sorted array.
>> If it is,  add this numeric value to your list of  "intersection
>> elements".
>>
>> As you pass through all elements of the 2nd array,  the values
>> found which
>> are intersecting need to be saved  ( maybe in the 1st arrays
>> space to save
>>  memory).   Ideally, these should be saved in sorted order as
>> they are found.
>>
>> ( how you store the sorted array will affect speed of this check
>> of course.
>>   I'd keep it simple on the 1st round, then optimize the code
>> once everything
>>   appears to be working well, ie with buckets or pointers or
>> whatever.  How
>>   you determine if an element in array 2 intersects with an
>> element of array
>>   1 will depend on how you store your sorted array.  You might do
>> a linear
>>   search or a binary search or a bucket search of some sort ).
>>
>> 3)  Now...  step through the 3rd array,  1 element at a time,  looking
>> to see if each
>>value is in the  just created  list  of   "intersection elements"
>>
>> 4)  Do the save thing now with each of the remaining original K
>> arrays.
>>
>> Dan:-)
>>
>>
>>
>> On Oct 24, 10:17 pm, kumar raja  wrote:
>> >  Find intersection of K unsorted array of N elements each. Intersection
>> > consists of elements that appear in all the K arrays.
>> >
>> > what data structure is useful here??
>> >
>> > --
>> > Regards
>> > Kumar Raja
>> > M.Tech(SIT)
>> > IIT Kharagpur,
>> > 10it60...@iitkgp.ac.in
>>
>> --
>> 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.
>>
>>
>
>
> --
> Anup Ghatage
>
>  --
> 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.
>



-- 
Nitin Garg

"Personality can open doors, but only Character can keep them open"

-- 
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.

Re: [algogeeks] Re: Intersection of arrays

[Anup Ghatage]

Don,
As you said, the intersection set, won't really be in sorted order as it
depends on the elements of the second array, which are unsorted. Still,
sorting them wouldn't be much different as it'd be worst case O(n logn).. [
Array 2 == Array 1 ]
But sorting the First Array has already cost O(n logn)

So I guess the worse case complexity has to be O(n logn) anyway..

On Thu, Oct 27, 2011 at 10:54 PM, Dan  wrote:

> Hashing all of the K arrays seems like a bit much.   How about this?
>
> You have  K  seperate arrays to start with,  each array having N
> elements (is that correct?).
>
> 1)  Sort the first array.
>
> 2)  Step through the 2nd array, 1 element at a time  say
> Array(2).element(i)
> Check to see if the value of  Array(2).element(i) is in the first
> sorted array.
> If it is,  add this numeric value to your list of  "intersection
> elements".
>
> As you pass through all elements of the 2nd array,  the values
> found which
> are intersecting need to be saved  ( maybe in the 1st arrays
> space to save
>  memory).   Ideally, these should be saved in sorted order as
> they are found.
>
> ( how you store the sorted array will affect speed of this check
> of course.
>   I'd keep it simple on the 1st round, then optimize the code
> once everything
>   appears to be working well, ie with buckets or pointers or
> whatever.  How
>   you determine if an element in array 2 intersects with an
> element of array
>   1 will depend on how you store your sorted array.  You might do
> a linear
>   search or a binary search or a bucket search of some sort ).
>
> 3)  Now...  step through the 3rd array,  1 element at a time,  looking
> to see if each
>value is in the  just created  list  of   "intersection elements"
>
> 4)  Do the save thing now with each of the remaining original K
> arrays.
>
> Dan:-)
>
>
>
> On Oct 24, 10:17 pm, kumar raja  wrote:
> >  Find intersection of K unsorted array of N elements each. Intersection
> > consists of elements that appear in all the K arrays.
> >
> > what data structure is useful here??
> >
> > --
> > Regards
> > Kumar Raja
> > M.Tech(SIT)
> > IIT Kharagpur,
> > 10it60...@iitkgp.ac.in
>
> --
> 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.
>
>


-- 
Anup Ghatage

-- 
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.

[algogeeks] Re: Intersection of arrays

[Dan]

Hashing all of the K arrays seems like a bit much.   How about this?

You have  K  seperate arrays to start with,  each array having N
elements (is that correct?).

1)  Sort the first array.

2)  Step through the 2nd array, 1 element at a time  say
Array(2).element(i)
 Check to see if the value of  Array(2).element(i) is in the first
sorted array.
 If it is,  add this numeric value to your list of  "intersection
elements".

 As you pass through all elements of the 2nd array,  the values
found which
 are intersecting need to be saved  ( maybe in the 1st arrays
space to save
  memory).   Ideally, these should be saved in sorted order as
they are found.

 ( how you store the sorted array will affect speed of this check
of course.
   I'd keep it simple on the 1st round, then optimize the code
once everything
   appears to be working well, ie with buckets or pointers or
whatever.  How
   you determine if an element in array 2 intersects with an
element of array
   1 will depend on how you store your sorted array.  You might do
a linear
   search or a binary search or a bucket search of some sort ).

3)  Now...  step through the 3rd array,  1 element at a time,  looking
to see if each
value is in the  just created  list  of   "intersection elements"

4)  Do the save thing now with each of the remaining original K
arrays.

Dan:-)



On Oct 24, 10:17 pm, kumar raja  wrote:
>  Find intersection of K unsorted array of N elements each. Intersection
> consists of elements that appear in all the K arrays.
>
> what data structure is useful here??
>
> --
> Regards
> Kumar Raja
> M.Tech(SIT)
> IIT Kharagpur,
> 10it60...@iitkgp.ac.in

-- 
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.