Re: [algogeeks] Re: Questions
cant we use knuth morris algorithm..to find pattern..in a row? On Thu, Oct 27, 2011 at 10:28 PM, Anup Ghatage ghat...@gmail.com wrote: I guess this is just like finding a word in a matrix On Thu, Oct 27, 2011 at 7:32 PM, SAMMM somnath.nit...@gmail.com wrote: Forgot to mention this was asked in Amazon Interview .. -- 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. -- *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.
Re: [algogeeks] Re: Intersection of arrays
The hashing solution is similar to the 1st answer herehttp://stackoverflow.com/questions/2932979/find-a-common-element-within-n-arrays A sorting solution will take O(k.n.logn) time On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage ghat...@gmail.com 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 dant...@aol.com 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 rajkumar.cs...@gmail.com 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.
[algogeeks] Re: Questions
How do u plan to implement it ??? -- 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
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 nitin.garg.i...@gmail.com wrote: The hashing solution is similar to the 1st answer herehttp://stackoverflow.com/questions/2932979/find-a-common-element-within-n-arrays A sorting solution will take O(k.n.logn) time On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage ghat...@gmail.com 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 dant...@aol.com 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 rajkumar.cs...@gmail.com 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: Find all possible combination of integers for a given sum
ohh , the number can repeat itself. I dint notice that.
On Fri, Oct 28, 2011 at 4:02 PM, mohit verma mohit89m...@gmail.com wrote:
something like this :
for(int i=0;temp=sum , isum/2;i++)
{ temp=temp-i;
for(int j=i+1;jtemp;j++)
couti j temp-j\n;
}
But there is a problem with code :
like for sum 7 , repeated cases are 0 3 4 and 0 4 3.
On Thu, Oct 27, 2011 at 7:46 PM, rj7 r4ra...@gmail.com wrote:
@Nitin Garg well if negatives are included there would be infinite
number of solutions
right?
and we can start we start with dividing the sum by combinations.
Atleast one number must be greater than sum/combination..
Am not sure it this is same as that subset manipulation...
pls post the algo for that recursion method!
On Oct 27, 12:21 am, Nitin Garg nitin.garg.i...@gmail.com wrote:
Are we talking about only positive integers here?
On Wed, Oct 26, 2011 at 11:33 PM, Vaibhav Mittal
vaibhavmitta...@gmail.comwrote:
+1 Prem
@ligerdave : I knew about the recursion method..but can u throw some
light
on the pointer based method..(with a small example maybe)..
Specifically I wanted to know the implementation part and the running
time
of the algorithm.
On Wed, Oct 26, 2011 at 8:33 PM, ligerdave david.c...@gmail.com
wrote:
@meng You already have the pattern figured out. each time subtract 1
from the lowest digit and add to higher digit(only once), until the
lowest digit equals to closest higher digit. the selection of which
number to start could be figured out with given parameters sum and
combination
@Prem, no recursion needed here. it make it more complex than
necessary. one loop with a pointer should be able to resolve this
On Oct 24, 6:28 pm, Meng Yan mengyan.fu...@gmail.com wrote:
Hi, my question is
given sum=N and combination constraint=M (the number of elements),
how
to
find all possible combinations of integers?
For example, given sum=6, combination=3; how to get the result as
following:
1+1+4;
1+2+3;
2+2+2;
We don't care about order of the elements, which means 1+1+4 and
1+4+1
are
considered as same combination.
Thanks a lot!
Meng
--
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.
--
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.
--
*MOHIT VERMA*
--
*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] Re: Find all possible combination of integers for a given sum
something like this :
for(int i=0;temp=sum , isum/2;i++)
{ temp=temp-i;
for(int j=i+1;jtemp;j++)
couti j temp-j\n;
}
But there is a problem with code :
like for sum 7 , repeated cases are 0 3 4 and 0 4 3.
On Thu, Oct 27, 2011 at 7:46 PM, rj7 r4ra...@gmail.com wrote:
@Nitin Garg well if negatives are included there would be infinite
number of solutions
right?
and we can start we start with dividing the sum by combinations.
Atleast one number must be greater than sum/combination..
Am not sure it this is same as that subset manipulation...
pls post the algo for that recursion method!
On Oct 27, 12:21 am, Nitin Garg nitin.garg.i...@gmail.com wrote:
Are we talking about only positive integers here?
On Wed, Oct 26, 2011 at 11:33 PM, Vaibhav Mittal
vaibhavmitta...@gmail.comwrote:
+1 Prem
@ligerdave : I knew about the recursion method..but can u throw some
light
on the pointer based method..(with a small example maybe)..
Specifically I wanted to know the implementation part and the running
time
of the algorithm.
On Wed, Oct 26, 2011 at 8:33 PM, ligerdave david.c...@gmail.com
wrote:
@meng You already have the pattern figured out. each time subtract 1
from the lowest digit and add to higher digit(only once), until the
lowest digit equals to closest higher digit. the selection of which
number to start could be figured out with given parameters sum and
combination
@Prem, no recursion needed here. it make it more complex than
necessary. one loop with a pointer should be able to resolve this
On Oct 24, 6:28 pm, Meng Yan mengyan.fu...@gmail.com wrote:
Hi, my question is
given sum=N and combination constraint=M (the number of elements),
how
to
find all possible combinations of integers?
For example, given sum=6, combination=3; how to get the result as
following:
1+1+4;
1+2+3;
2+2+2;
We don't care about order of the elements, which means 1+1+4 and
1+4+1
are
considered as same combination.
Thanks a lot!
Meng
--
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.
--
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.
--
*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] Re: Modified binary search
+1 Gene With regards, Praveen Raj DCE-IT 3rd yr 735993 praveen0...@gmail.com On Wed, Sep 28, 2011 at 1:36 AM, Gene gene.ress...@gmail.com wrote: Indeed you must be given that all the array elements are unique or at least that there are no more than floor(n/2) repeats). Otherwise this is impossible. The simplest way to think about it is first to search for i such that a[i] a[i+1]. At that point you know there are two sorted ranges a[0]..a[i] and a[i+1] to a[n-1], so you can use regular binary search on each of these pieces. So how to find i? This is itself a binary search. At each stage, check whether a[0] a[mid] and a[mid] a[n-1]. The half that passes this test contains i. So throw away the other. On Sep 27, 10:01 am, Decipher ankurseth...@gmail.com wrote: A given sorted array is rotated unknown number of times , write a C/C++ code to find an element in the sorted array in O(log n) time . I know the solution to this problem is through binary search , but don't know the exact solution . Please help !! -- 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. -- 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
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 rajkumar.cs...@gmail.com 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 nitin.garg.i...@gmail.com wrote: The hashing solution is similar to the 1st answer herehttp://stackoverflow.com/questions/2932979/find-a-common-element-with... A sorting solution will take O(k.n.logn) time On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage ghat...@gmail.com 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 dant...@aol.com 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 rajkumar.cs...@gmail.com 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
[algogeeks] Re: Intersection of arrays
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 rajkumar.cs...@gmail.com 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 nitin.garg.i...@gmail.com wrote: The hashing solution is similar to the 1st answer herehttp://stackoverflow.com/questions/2932979/find-a-common-element-with... A sorting solution will take O(k.n.logn) time On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage ghat...@gmail.com 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 dant...@aol.com 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 rajkumar.cs...@gmail.com 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
Re: [algogeeks] Re: Directi Questions - needed answers
@ankur - Ans-9 how can it be log n. The heap given is Max heap. I think it
should be O(n) using array or tree traversal (as heap is implemented)
keeping current min at hand. Correct me if m wrong.
On Sat, Oct 15, 2011 at 12:14 PM, shady sinv...@gmail.com wrote:
already been answered... :-/
but have to say you are damn quick...
On Sat, Oct 15, 2011 at 12:03 PM, Bittu Sarkar bittu...@gmail.com wrote:
Q7. Correct answer is 12km west and 12km south for sure!!
On 21 September 2011 13:28, Nitin Garg nitin.garg.i...@gmail.com wrote:
Ohh i totally missed that line.
Thanx a lot :)
On Wed, Sep 21, 2011 at 10:46 AM, pankaj agarwal
agarwal.pankaj.1...@gmail.com wrote:
@Nitin Garg
Question 6 -
i agree that greater the sum is and greater the probability to getting
it.
but in given question if sum100 then rolling is stopped
so for
P(106)=P(100)*1/6
P(105)=P(100)*1/6+P(99)*1/6
.
.
.
P(101)=P(100)*1/6+P(99)*(1/6)+P(98)*(1/6)+P(97)*(1/6)+..+P(95)*(1/6)
now P(101) is more
cleare me if something is wrong.
On Mon, Sep 19, 2011 at 1:35 PM, Nitin Garg
nitin.garg.i...@gmail.comwrote:
Question 6 -
Intuitively you can see that the greater the sum is, the greater the
favorable events in sample space.
e.g. - sum = 1 .. cases {(1)} Pr = 1/6
sum = 2 cases {(2),(1,1)} Pr = 1/6 + 1/36
sum = 3cases {(3),(2,1)(1,2)(1,1,1)} Pr = 1/6 + 1/36 +1/36
+ 1/216
for a more formal proof, look at the recursion -
P(k) = (P(k-6) + P(k-5) + P(k-4)... P(k-1)))/6
where P(0) = 1, P(i) = 0 for i0
Base case -
P(2) P(1)
Hypothesis -
P(i) P(i-1) for all i = k
To prove
P(k+1) P(k)
Proof
P(k+1) - P(k) = (P(k) - P(k-6))/6 0
--
Pankaj Agarwal
Communication and Computer Engineering
LNMIIT,jaipur
--
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.
--
Bittu Sarkar
5th Year Dual Degree Student
Department of Computer Science Engineering
Indian Institute of Technology Kharagpur
--
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.
--
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
--
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] Coprime Numbers
If a natural number N is given such that N = a × b where a and b are the factors of N. How many such sets of (a, b) can be formed in which the selection of the two numbers a and b is distinctly different if N = 8 × 33 and the distinct factors should be Prime to each other ? -- 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: Directi Questions - needed answers
@Mohit
Agreed. The answer is O(n).
On Fri, Oct 28, 2011 at 6:48 PM, mohit verma mohit89m...@gmail.com wrote:
@ankur - Ans-9 how can it be log n. The heap given is Max heap. I think
it should be O(n) using array or tree traversal (as heap is implemented)
keeping current min at hand. Correct me if m wrong.
On Sat, Oct 15, 2011 at 12:14 PM, shady sinv...@gmail.com wrote:
already been answered... :-/
but have to say you are damn quick...
On Sat, Oct 15, 2011 at 12:03 PM, Bittu Sarkar bittu...@gmail.comwrote:
Q7. Correct answer is 12km west and 12km south for sure!!
On 21 September 2011 13:28, Nitin Garg nitin.garg.i...@gmail.comwrote:
Ohh i totally missed that line.
Thanx a lot :)
On Wed, Sep 21, 2011 at 10:46 AM, pankaj agarwal
agarwal.pankaj.1...@gmail.com wrote:
@Nitin Garg
Question 6 -
i agree that greater the sum is and greater the probability to getting
it.
but in given question if sum100 then rolling is stopped
so for
P(106)=P(100)*1/6
P(105)=P(100)*1/6+P(99)*1/6
.
.
.
P(101)=P(100)*1/6+P(99)*(1/6)+P(98)*(1/6)+P(97)*(1/6)+..+P(95)*(1/6)
now P(101) is more
cleare me if something is wrong.
On Mon, Sep 19, 2011 at 1:35 PM, Nitin Garg nitin.garg.i...@gmail.com
wrote:
Question 6 -
Intuitively you can see that the greater the sum is, the greater the
favorable events in sample space.
e.g. - sum = 1 .. cases {(1)} Pr = 1/6
sum = 2 cases {(2),(1,1)} Pr = 1/6 + 1/36
sum = 3cases {(3),(2,1)(1,2)(1,1,1)} Pr = 1/6 + 1/36
+1/36 + 1/216
for a more formal proof, look at the recursion -
P(k) = (P(k-6) + P(k-5) + P(k-4)... P(k-1)))/6
where P(0) = 1, P(i) = 0 for i0
Base case -
P(2) P(1)
Hypothesis -
P(i) P(i-1) for all i = k
To prove
P(k+1) P(k)
Proof
P(k+1) - P(k) = (P(k) - P(k-6))/6 0
--
Pankaj Agarwal
Communication and Computer Engineering
LNMIIT,jaipur
--
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.
--
Bittu Sarkar
5th Year Dual Degree Student
Department of Computer Science Engineering
Indian Institute of Technology Kharagpur
--
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.
--
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
--
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.
--
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
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 rajkumar.cs...@gmail.com 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.
Re: [algogeeks] c output
can u plz tell me what exactly %*d means? -- 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: Amazon OS question
How are we going to write a program which if fed the data gives the answer? Any ideas for the algorithm? My approach: We have a graph here. We have vertices with indegree 0 and outdegree 1. - call it set A (start points) (m vertices) We have vertices with indegree 1 and outdegree 0. - call it set B (end points) (n vertices) The paths from set A to set B can be run on multiple processors (m x n paths possible). if no. of processors = m x n then no. of steps will be maximum no. of elements in any path. In the above ques, m = 1 and n = 3. if no. of processors m x n, then run a BFS on the graph and find the number of vertices at each level. In the above question, the vertices at levels are 1, 1, 3 , 1. ((Max of these i.e. 3) / number of processors) + maximum no. of elements in any path = would be the answer. Now this part would have a problem if m!=1; Another problem would be how to find the maximum no. of elements in any path possible. On Sep 25, 9:03 am, sivaviknesh s sivavikne...@gmail.com wrote: A parallel program consists of 8 tasks – T1 through T8. Each task requires one time step to be executed on a single processor. Let X - Y denote the fact that task X must be executed before task Y is executed. Suppose only the tasks X, Y are to be executed. On any multiprocessor machine it would require at least 2 time steps since in the first step X could be executed, and Y could be executed in the next time step (since it requires X to complete first). Now, suppose the following dependencies exist between the tasks T1 – T8: T1 - T2 T2 - T3 T3 - T6 T2 - T4 T4 - T7 T2 - T5 T5 - T8 What is the minimum number of time steps required to execute these 8 tasks on a 2 processor machine and a 4 processor machine? a)4 2 b)5 2 c)5 4 d)6 2 -- Regards, $iva -- 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] Suffix tree and Tournament Tree creation
Can any one give the pseudo code for creating suffix and tournament tree ??? Not able to find the proper algo in the net ,. tht's y asking for help . plzz -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/IkGRDvnu5pgJ. 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] c output
let this statement int x=100,y=5;printf(%*d,x,y); in this line first x is assign to '*' and it become %100d and it will padd 100 spaces before print. and if we use( %*d,x) then x is assign to '*' and garbage value wud be printed. On Fri, Oct 28, 2011 at 8:53 PM, annarao kataru kataruanna...@gmail.comwrote: can u plz tell me what exactly %*d means? -- 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. -- AMRIT -- 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
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 duman...@gmail.com 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 rajkumar.cs...@gmail.com 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.
Re: [algogeeks] Coprime Numbers
Any natural no can be written as a product of powers of primes N = a^m × b^n × c^l where a, b , c are prime no.s for given N= 8 × 33 N= 2^3 × 3^1 × 11^1 now we can use combinatorics to find 2 distinct factors a × b such that (a,m)=1 i.e. they are co-primes On 28 October 2011 20:21, SAMMM somnath.nit...@gmail.com wrote: If a natural number N is given such that N = a × b where a and b are the factors of N. How many such sets of (a, b) can be formed in which the selection of the two numbers a and b is distinctly different if N = 8 × 33 and the distinct factors should be Prime to each other ? -- 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. -- 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: Coprime Numbers
@Sammm: Suppose that N has prime factorization N = p1^e1 * p2^e2 * ... * pn^en where ^ indicates exponentiation. Then for a and b to be coprime, a must contain all or none of the factors of each prime, and similarly for b. Thus, a is the product of some subset of the pi^ei and b is the product of the complementary subset. If in your example you regard (33,8) as different from (8,33), then there are 2^n coprime factors (a,b); otherwise there are 2^(n-1) coprime factors. In your example above, N = 2^3 * 3 * 11, so n = 3. The factors are (1,264), (3,88), (8,33), (11,24), and their reverses, if you count the reverses as distinct. Here I have used that 1 is considered coprime to every integer. Dave On Oct 28, 9:51 am, SAMMM somnath.nit...@gmail.com wrote: If a natural number N is given such that N = a × b where a and b are the factors of N. How many such sets of (a, b) can be formed in which the selection of the two numbers a and b is distinctly different if N = 8 × 33 and the distinct factors should be Prime to each other ? -- 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: Amazon OS question
I think 5,4 On Fri, Oct 28, 2011 at 9:08 PM, Dumanshu duman...@gmail.com wrote: How are we going to write a program which if fed the data gives the answer? Any ideas for the algorithm? My approach: We have a graph here. We have vertices with indegree 0 and outdegree 1. - call it set A (start points) (m vertices) We have vertices with indegree 1 and outdegree 0. - call it set B (end points) (n vertices) The paths from set A to set B can be run on multiple processors (m x n paths possible). if no. of processors = m x n then no. of steps will be maximum no. of elements in any path. In the above ques, m = 1 and n = 3. if no. of processors m x n, then run a BFS on the graph and find the number of vertices at each level. In the above question, the vertices at levels are 1, 1, 3 , 1. ((Max of these i.e. 3) / number of processors) + maximum no. of elements in any path = would be the answer. Now this part would have a problem if m!=1; Another problem would be how to find the maximum no. of elements in any path possible. On Sep 25, 9:03 am, sivaviknesh s sivavikne...@gmail.com wrote: A parallel program consists of 8 tasks – T1 through T8. Each task requires one time step to be executed on a single processor. Let X - Y denote the fact that task X must be executed before task Y is executed. Suppose only the tasks X, Y are to be executed. On any multiprocessor machine it would require at least 2 time steps since in the first step X could be executed, and Y could be executed in the next time step (since it requires X to complete first). Now, suppose the following dependencies exist between the tasks T1 – T8: T1 - T2 T2 - T3 T3 - T6 T2 - T4 T4 - T7 T2 - T5 T5 - T8 What is the minimum number of time steps required to execute these 8 tasks on a 2 processor machine and a 4 processor machine? a)4 2 b)5 2 c)5 4 d)6 2 -- Regards, $iva -- 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. -- navneet singh gaur -- 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.
