Re: [algogeeks] Intersection of arrays
I think , in the worst case this hashing technique 'll take O(n^(k-1)) time? so i wud stick with sorting idea with confirm : O(mlogm) + O(m) time complexity where m is avg length of arrays. On Tue, Oct 25, 2011 at 6:02 PM, kumar raja wrote: > Dheeraj can u please tell me how to keep track count for an element ,in > hash table. > I want the exact structure of the hash table > The hash function uses the input as the elements value ,and stores it in > some slot by computing hash function..then where is the question of > storing count for that number. > > I am pretty much confused with this hashing and how these details are > exactly implemented in STL hash map class. > > On 24 October 2011 23:32, Dheeraj Sharma wrote: > >> use hashing.. >> let the no. of array be 1 to K >> increment the count of element for that array..(in hash table) only if its >> count value in hash table is one less then the array no.(which means >> that..it is present in all the arrays..preceding it) >> now search the hash table..in which element count is equal to K >> >> >> On Tue, Oct 25, 2011 at 11:47 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. >>> >> >> >> >> -- >> *Dheeraj Sharma* >> >> >> -- >> 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. > -- *MOHIT VERMA* -- 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] Intersection of arrays
I have got an idea I will construct (k-1) hash tables for the 2 to k array elements. Now starting at the 1st element in 1st array i will search for it in all the (k-1) hash tables in O((k-1)*1) time. So for n elements it would take O( n*(k-1)) time.. Is my approach correct,please correct me if i am wrong... and two questions which are bothering me are 1)Does the space complexity in hash table to store all the 'n' elements is O(n) ?? i want the correct value. 2)what is the time complexity to search in hash table if 'n' numbers are stored .Is it still O(1) ??? i dont know how it is O(1) exactly it is a guess. On 24 October 2011 23:32, Dheeraj Sharma wrote: > use hashing.. > let the no. of array be 1 to K > increment the count of element for that array..(in hash table) only if its > count value in hash table is one less then the array no.(which means > that..it is present in all the arrays..preceding it) > now search the hash table..in which element count is equal to K > > > On Tue, Oct 25, 2011 at 11:47 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. >> > > > > -- > *Dheeraj Sharma* > > > -- > 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] Intersection of arrays
Dheeraj can u please tell me how to keep track count for an element ,in hash table. I want the exact structure of the hash table The hash function uses the input as the elements value ,and stores it in some slot by computing hash function..then where is the question of storing count for that number. I am pretty much confused with this hashing and how these details are exactly implemented in STL hash map class. On 24 October 2011 23:32, Dheeraj Sharma wrote: > use hashing.. > let the no. of array be 1 to K > increment the count of element for that array..(in hash table) only if its > count value in hash table is one less then the array no.(which means > that..it is present in all the arrays..preceding it) > now search the hash table..in which element count is equal to K > > > On Tue, Oct 25, 2011 at 11:47 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. >> > > > > -- > *Dheeraj Sharma* > > > -- > 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] Intersection of arrays
use hashing.. let the no. of array be 1 to K increment the count of element for that array..(in hash table) only if its count value in hash table is one less then the array no.(which means that..it is present in all the arrays..preceding it) now search the hash table..in which element count is equal to K On Tue, Oct 25, 2011 at 11:47 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. > -- *Dheeraj Sharma* -- 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] Intersection of arrays
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.
