Re: [algogeeks] Yahoo coding round question
I'm not sure what a 2 hash table is. Can you please explain ? On Tue, Oct 19, 2010 at 10:36 PM, MOHIT mohit...@gmail.com wrote: o(n) soln Lets say A is the array of length N. Create an array sum of length N and initialize it to 0. Create an array product of length N and initialize it to 1. now sum[i]=sum[i-1]+A[i]; sum[0]=A[0]; product[i]=product[i-1]+A[I]product[0]=A[0]; make a two hash table for product and sum array ; in product arrary traverse i=0 to n ; divide result=product[i]/P and check result is present in hash table or not if yes then get index of result . suppose k then checkabsolute(sum[i]-sum[k])==S if yes then we got sub array. else ..keep do this untill array end ; -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Yahoo coding round question
On Wed, Oct 20, 2010 at 5:11 AM, Kishen Das kishen@gmail.com wrote: In the below code the jth and kth inner for loops can be run in parallel making them O(1) and the entire thing O(n). for ( i=0 to i=N-1 ) { for ( j = i to j = 0 ) { why till 0? if S=107 , P= 210 and array is 10, -3 , 2 , 105, 13 code will fail sum[j] += A[ i] product[j] *= A [ i] } for( k=0 to k= i ) if ( sum[k] == S and product[k] == P ) { Answer is the sub array A[k to i ] break } } Kishen On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh iiita2007...@gmail.comwrote: @ Rahul patil ofcourse array may have negative or positive integers @ Kishen both O(n) and O(n logn) solutions was asked in this yahoo coding round question On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh iiita2007...@gmail.com wrote: Given an array of length N. How will you find the minimum length contiguous sub - array of whose sum is S and whose product is P . Here S and P will be given to you. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ABHISHEK KUMAR SINGH BTECH (INFORMATION TECHNOLOGY) IIIT ALLAHABAD 9956640538 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Rahul Patil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Yahoo coding round question
@rahul the code doesn't fail for the case you gave. Please check. Also Kishen can you explain how is the complexity for two loops runninf in parallel equal to O(1). On Wed, Oct 20, 2010 at 3:06 PM, rahul patil rahul.deshmukhpa...@gmail.comwrote: On Wed, Oct 20, 2010 at 5:11 AM, Kishen Das kishen@gmail.com wrote: In the below code the jth and kth inner for loops can be run in parallel making them O(1) and the entire thing O(n). for ( i=0 to i=N-1 ) { for ( j = i to j = 0 ) { why till 0? if S=107 , P= 210 and array is 10, -3 , 2 , 105, 13 code will fail sum[j] += A[ i] product[j] *= A [ i] } for( k=0 to k= i ) if ( sum[k] == S and product[k] == P ) { Answer is the sub array A[k to i ] break } } Kishen On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh iiita2007...@gmail.comwrote: @ Rahul patil ofcourse array may have negative or positive integers @ Kishen both O(n) and O(n logn) solutions was asked in this yahoo coding round question On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh iiita2007...@gmail.com wrote: Given an array of length N. How will you find the minimum length contiguous sub - array of whose sum is S and whose product is P . Here S and P will be given to you. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ABHISHEK KUMAR SINGH BTECH (INFORMATION TECHNOLOGY) IIIT ALLAHABAD 9956640538 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Rahul Patil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Yahoo coding round question
@Kishen: Plz explain the complexity... On 10/20/10, Lily Aldrin lily.hi...@gmail.com wrote: @rahul the code doesn't fail for the case you gave. Please check. Also Kishen can you explain how is the complexity for two loops runninf in parallel equal to O(1). On Wed, Oct 20, 2010 at 3:06 PM, rahul patil rahul.deshmukhpa...@gmail.comwrote: On Wed, Oct 20, 2010 at 5:11 AM, Kishen Das kishen@gmail.com wrote: In the below code the jth and kth inner for loops can be run in parallel making them O(1) and the entire thing O(n). for ( i=0 to i=N-1 ) { for ( j = i to j = 0 ) { why till 0? if S=107 , P= 210 and array is 10, -3 , 2 , 105, 13 code will fail sum[j] += A[ i] product[j] *= A [ i] } for( k=0 to k= i ) if ( sum[k] == S and product[k] == P ) { Answer is the sub array A[k to i ] break } } Kishen On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh iiita2007...@gmail.comwrote: @ Rahul patil ofcourse array may have negative or positive integers @ Kishen both O(n) and O(n logn) solutions was asked in this yahoo coding round question On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh iiita2007...@gmail.com wrote: Given an array of length N. How will you find the minimum length contiguous sub - array of whose sum is S and whose product is P . Here S and P will be given to you. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ABHISHEK KUMAR SINGH BTECH (INFORMATION TECHNOLOGY) IIIT ALLAHABAD 9956640538 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Rahul Patil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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 algoge...@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] Yahoo coding round question
for ( i=0 to i=N-1 ) { // This inner for-loop can be run in parallel, as there is no dependency wrt previously computed values or the values at other indices. // you are just blindly adding the value at A[i] to all the elements of the sub-array B[0 - j ] and hence can be run in parallel. for ( j = i to j = 0 ) { sum[j] = sum[j] + A[ i] product[j]= product[j] * A [i] if ( sum[j]==sum and product[j] ==product ) Answer is A [ j to i ] } } Kishen On Wed, Oct 20, 2010 at 12:34 PM, Lily Aldrin lily.hi...@gmail.com wrote: @rahul the code doesn't fail for the case you gave. Please check. Also Kishen can you explain how is the complexity for two loops runninf in parallel equal to O(1). On Wed, Oct 20, 2010 at 3:06 PM, rahul patil rahul.deshmukhpa...@gmail.com wrote: On Wed, Oct 20, 2010 at 5:11 AM, Kishen Das kishen@gmail.com wrote: In the below code the jth and kth inner for loops can be run in parallel making them O(1) and the entire thing O(n). for ( i=0 to i=N-1 ) { for ( j = i to j = 0 ) { why till 0? if S=107 , P= 210 and array is 10, -3 , 2 , 105, 13 code will fail sum[j] += A[ i] product[j] *= A [ i] } for( k=0 to k= i ) if ( sum[k] == S and product[k] == P ) { Answer is the sub array A[k to i ] break } } Kishen On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh iiita2007...@gmail.com wrote: @ Rahul patil ofcourse array may have negative or positive integers @ Kishen both O(n) and O(n logn) solutions was asked in this yahoo coding round question On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh iiita2007...@gmail.com wrote: Given an array of length N. How will you find the minimum length contiguous sub - array of whose sum is S and whose product is P . Here S and P will be given to you. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ABHISHEK KUMAR SINGH BTECH (INFORMATION TECHNOLOGY) IIIT ALLAHABAD 9956640538 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Rahul Patil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Yahoo coding round question
I am running my algorithm for your values - I will just show it for sum. Array B [ 0 0 0 0 0 ] i = 0 Array B [ 10 0 0 0 0 ] i = 1 Array B [7 -3 0 0 0 ] i = 2 Array B [ 9 -1 2 0 0 ] i=3 Array B [ 116 104 107 105 0 ] You will stop here and the answer is the range [ k to i ] which is A [ 2 to 3 ] I am attaching the modified algorithm. - for ( i=0 to i=N-1 ) { for ( j = i to j = 0 ) { sum[j] = sum[j] + A[ i] product[j]= product[j] * A [i] if ( sum[j]==sum and product[j] ==product ) Answer is A [ j to i ] } } You can even flag the indexes whose sum or product exceeds the requirement, so that you don't add or multiply at these indexes in the next set of iterations, making it even more efficient algorithm. Negative values do not affect this algorithm. Kishen On Wed, Oct 20, 2010 at 4:36 AM, rahul patil rahul.deshmukhpa...@gmail.comwrote: On Wed, Oct 20, 2010 at 5:11 AM, Kishen Das kishen@gmail.com wrote: In the below code the jth and kth inner for loops can be run in parallel making them O(1) and the entire thing O(n). for ( i=0 to i=N-1 ) { for ( j = i to j = 0 ) { why till 0? if S=107 , P= 210 and array is 10, -3 , 2 , 105, 13 code will fail sum[j] += A[ i] product[j] *= A [ i] } for( k=0 to k= i ) if ( sum[k] == S and product[k] == P ) { Answer is the sub array A[k to i ] break } } Kishen On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh iiita2007...@gmail.comwrote: @ Rahul patil ofcourse array may have negative or positive integers @ Kishen both O(n) and O(n logn) solutions was asked in this yahoo coding round question On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh iiita2007...@gmail.com wrote: Given an array of length N. How will you find the minimum length contiguous sub - array of whose sum is S and whose product is P . Here S and P will be given to you. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ABHISHEK KUMAR SINGH BTECH (INFORMATION TECHNOLOGY) IIIT ALLAHABAD 9956640538 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Rahul Patil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Yahoo coding round question
Given an array of length N. How will you find the minimum length contiguous sub - array of whose sum is S and whose product is P . Here S and P will be given to you. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Yahoo coding round question
Does array consists of negative nos? On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh iiita2007...@gmail.com wrote: Given an array of length N. How will you find the minimum length contiguous sub - array of whose sum is S and whose product is P . Here S and P will be given to you. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Rahul Patil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Yahoo coding round question
Lets say A is the array of length N. Create an array sum of length N and initialize it to 0. Create an array product of length N and initialize it to 1. for ( i=0 to i=N-1 ) { for ( j = i to j = 0 ) { sum[j] = sum[j] + A[ i] product[j]= product[j] * A [i] } for( k=0 to k= i ) if ( sum[k] == S and product[k] == P ) { Answer is the sub array A[k to i ] break } } Kishen On Tue, Oct 19, 2010 at 2:58 AM, Abhishek Kumar Singh iiita2007...@gmail.com wrote: Given an array of length N. How will you find the minimum length contiguous sub - array of whose sum is S and whose product is P . Here S and P will be given to you. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Yahoo coding round question
@ Rahul patil ofcourse array may have negative or positive integers @ Kishen both O(n) and O(n logn) solutions was asked in this yahoo coding round question On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh iiita2007...@gmail.com wrote: Given an array of length N. How will you find the minimum length contiguous sub - array of whose sum is S and whose product is P . Here S and P will be given to you. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ABHISHEK KUMAR SINGH BTECH (INFORMATION TECHNOLOGY) IIIT ALLAHABAD 9956640538 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Yahoo coding round question
In the below code the jth and kth inner for loops can be run in parallel making them O(1) and the entire thing O(n). for ( i=0 to i=N-1 ) { for ( j = i to j = 0 ) { sum[j] += A[ i] product[j] *= A [ i] } for( k=0 to k= i ) if ( sum[k] == S and product[k] == P ) { Answer is the sub array A[k to i ] break } } Kishen On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh iiita2007...@gmail.comwrote: @ Rahul patil ofcourse array may have negative or positive integers @ Kishen both O(n) and O(n logn) solutions was asked in this yahoo coding round question On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh iiita2007...@gmail.com wrote: Given an array of length N. How will you find the minimum length contiguous sub - array of whose sum is S and whose product is P . Here S and P will be given to you. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ABHISHEK KUMAR SINGH BTECH (INFORMATION TECHNOLOGY) IIIT ALLAHABAD 9956640538 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Yahoo coding round question
o(n) soln Lets say A is the array of length N. Create an array sum of length N and initialize it to 0. Create an array product of length N and initialize it to 1. now sum[i]=sum[i-1]+A[i]; sum[0]=A[0]; product[i]=product[i-1]+A[I]product[0]=A[0]; make a two hash table for product and sum array ; in product arrary traverse i=0 to n ; divide result=product[i]/P and check result is present in hash table or not if yes then get index of result . suppose k then checkabsolute(sum[i]-sum[k])==S if yes then we got sub array. else ..keep do this untill array end ; -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Yahoo coding round question
Find the longest common subsequence of given N strings each having length between 0 to M. Can anybody give a good approach to the solutions -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Yahoo coding round question
pls check cormen i think thats most efficicent ...check under DP chapter On Sat, May 8, 2010 at 2:30 PM, Jitendra Kushwaha jitendra.th...@gmail.comwrote: Find the longest common subsequence of given N strings each having length between 0 to M. Can anybody give a good approach to the solutions -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Yahoo coding round question
I don't think DP is a good strategy for the N strings case 2010/5/8 sharad kumar aryansmit3...@gmail.com pls check cormen i think thats most efficicent ...check under DP chapter On Sat, May 8, 2010 at 2:30 PM, Jitendra Kushwaha jitendra.th...@gmail.com wrote: Find the longest common subsequence of given N strings each having length between 0 to M. Can anybody give a good approach to the solutions -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.