Re: [algogeeks] Re: Yahoo coding round question
@Kishen
The inner while loop increments the lower bound from where we are taking
product and sum. Total number of iterations of inner while loop can be n in
the worst case (when magnitude of last element is greater than that of given
product). So the array will be traversed twice.
Thanks,
- Ravindra
On Thu, Oct 28, 2010 at 12:38 AM, Kishen Das wrote:
> How do you claim that its O(n) when you have a while-loop inside the
> for-loop?
> What is the complexity of the inner while loop ?
>
> What is the worst case complexity, if only the last element of the array
> matches the product and the sum?
>
> Kishen
>
> On Wed, Oct 27, 2010 at 2:01 PM, ravindra patel
> wrote:
>
>> Here is a simple implementation. Complexity O(n). Please let me know if
>> you find any issues with this.
>>
>> Assumptions as stated in original problem -
>> 1- Required sub array is contiguous
>> 2- Given array has only integers (+ve and -)
>>
>>
>> // Params are array arr, length of array n, given sum and product
>> void subarr( int* arr, int n, int sum, int prod)
>> {
>> int lb = 0; // Lower bound of sub array
>> int s = 0; // Temporary sum
>> int p = 1; // Temporary prod
>>
>> int mod_p = (prod > 0) ? prod : (prod * -1); // |prod|
>> int min_p = mod_p * -1; // -|prod|
>> int i=0;
>> int found = 0;
>>
>> for(i=0; i> {
>> // Zero can't be sub array element if given product in not zero
>> if((arr[i] == 0) && (prod != 0))
>> {
>> lb = i+1;
>> s = 0;
>> p = 1;
>> continue;
>> }
>> s += arr[i];
>> p *= arr[i];
>>
>> // If product is out of range bring it back in
>> while (p < min_p || p > mod_p)
>> {
>> p /= arr[lb];
>> s -= arr[lb];
>> lb++;
>> }
>>
>> if( s== sum && p == prod)
>> {
>> printf ("Sub array is from index %d to %d\n", lb, i);
>> found = 1;
>> break;
>> }
>> }
>> if(!found)
>> printf("No Matching sub-array found\n");
>> }
>>
>>
>> Thanks,
>> - Ravindra
>>
>> On Mon, Oct 25, 2010 at 2:04 AM, Kishen Das wrote:
>>
>>> @Ravindra, Ligerdave
>>> You guys are all right. But with GPUs, you can literally have thousands
>>> of threads running in parallel.
>>> Again, my aim was not to prove that my O(n ^ 2) algorithm is O ( n) on a
>>> single processor system.
>>> It was more towards making the members of this group to think on the
>>> lines of Parallelism.
>>> I long back agreed that the worst case for my algorithm is O(n^2 ) on
>>> single processor systems.
>>>
>>> The current problem is a variation of original subset problem which is
>>> NP-complete. ( http://en.wikipedia.org/wiki/Subset_sum_problem )
>>>
>>> I really appreciate a O(n) solution to this problem on a single-processor
>>> system.
>>>
>>> Kishen
>>>
>>> On Sun, Oct 24, 2010 at 1:50 PM, ravindra patel <
>>> ravindra.it...@gmail.com> wrote:
>>>
>> It has nothing to do with time complexity.
My bad. Wrong choice of words. So in the PRAM model you can say the
time complexity is O(1), a pure theoretical concept. But the cost still
remains O(n), isn't it.
I guess now onwards we'll have to specifically ask interviewers whether
they are asking for time complexity on scalar machine or on a parallel
machine. Unless specified otherwise, my assumption by default would be a
scalar one though.
- Ravindra
On Sun, Oct 24, 2010 at 11:50 PM, ravindra patel <
ravindra.it...@gmail.com> wrote:
> @ Kishen
> So lets say you have 100 parallel processors and you are given an array
> of 100 elements, then the loop will execute in 1 clock. Now lets say on
> the
> same machine you are given a problem array of 1 million elements. So how
> many clocks are you gonna consume, assuming all your 100 processors are
> running in parallel.
>
> Buddy, with parallel processors you can reduce total computation time
> at most by a factor of number of processors you have (which will always
> be a
> constant, no matter how big it is). It has nothing to do with time
> complexity.
>
> Thanks,
> - Ravindra
>
>
> On Fri, Oct 22, 2010 at 8:17 AM, Kishen Das wrote:
>
>> Ok, if you look at the inner loop, it is -
>>
>> for ( j = i to j = 0 ) {
>> sum[j] += A[ i]
>> product[j] *= A [ i]
>> }
>>
>> This is as good as executing -
>> sum[i] = sum [ i ] + A[ i ] ---> ( 1 )
>> sum[i-1]= sum[i-1]+ A[i] > ( 2 )
>> --
>> ---
>> ---
>> sum[0] = sum[ 0]+A[i] --> ( i )
>>
>> Each of these assignments doesn't have any dependency with other
>> computations i.e.,
>> ( 1 ) is independent of ( 2 ) to ( i ) and so does ( 2 ) , ( 3 ) ,
>> ( i )
>> and hence each of this can be assigned to a different processor.
>> So, each of these statements( iterations) of the inner-loop j can be
>> run in different proc
Re: [algogeeks] Re: Yahoo coding round question
How do you claim that its O(n) when you have a while-loop inside the
for-loop?
What is the complexity of the inner while loop ?
What is the worst case complexity, if only the last element of the array
matches the product and the sum?
Kishen
On Wed, Oct 27, 2010 at 2:01 PM, ravindra patel wrote:
> Here is a simple implementation. Complexity O(n). Please let me know if you
> find any issues with this.
>
> Assumptions as stated in original problem -
> 1- Required sub array is contiguous
> 2- Given array has only integers (+ve and -)
>
>
> // Params are array arr, length of array n, given sum and product
> void subarr( int* arr, int n, int sum, int prod)
> {
> int lb = 0; // Lower bound of sub array
> int s = 0; // Temporary sum
> int p = 1; // Temporary prod
>
> int mod_p = (prod > 0) ? prod : (prod * -1); // |prod|
> int min_p = mod_p * -1; // -|prod|
> int i=0;
> int found = 0;
>
> for(i=0; i {
> // Zero can't be sub array element if given product in not zero
> if((arr[i] == 0) && (prod != 0))
> {
> lb = i+1;
> s = 0;
> p = 1;
> continue;
> }
> s += arr[i];
> p *= arr[i];
>
> // If product is out of range bring it back in
> while (p < min_p || p > mod_p)
> {
> p /= arr[lb];
> s -= arr[lb];
> lb++;
> }
>
> if( s== sum && p == prod)
> {
> printf ("Sub array is from index %d to %d\n", lb, i);
> found = 1;
> break;
> }
> }
> if(!found)
> printf("No Matching sub-array found\n");
> }
>
>
> Thanks,
> - Ravindra
>
> On Mon, Oct 25, 2010 at 2:04 AM, Kishen Das wrote:
>
>> @Ravindra, Ligerdave
>> You guys are all right. But with GPUs, you can literally have thousands of
>> threads running in parallel.
>> Again, my aim was not to prove that my O(n ^ 2) algorithm is O ( n) on a
>> single processor system.
>> It was more towards making the members of this group to think on the lines
>> of Parallelism.
>> I long back agreed that the worst case for my algorithm is O(n^2 ) on
>> single processor systems.
>>
>> The current problem is a variation of original subset problem which is
>> NP-complete. ( http://en.wikipedia.org/wiki/Subset_sum_problem )
>>
>> I really appreciate a O(n) solution to this problem on a single-processor
>> system.
>>
>> Kishen
>>
>> On Sun, Oct 24, 2010 at 1:50 PM, ravindra patel > > wrote:
>>
>>> >> It has nothing to do with time complexity.
>>> My bad. Wrong choice of words. So in the PRAM model you can say the time
>>> complexity is O(1), a pure theoretical concept. But the cost still remains
>>> O(n), isn't it.
>>>
>>> I guess now onwards we'll have to specifically ask interviewers whether
>>> they are asking for time complexity on scalar machine or on a parallel
>>> machine. Unless specified otherwise, my assumption by default would be a
>>> scalar one though.
>>>
>>> - Ravindra
>>>
>>>
>>> On Sun, Oct 24, 2010 at 11:50 PM, ravindra patel <
>>> ravindra.it...@gmail.com> wrote:
>>>
@ Kishen
So lets say you have 100 parallel processors and you are given an array
of 100 elements, then the loop will execute in 1 clock. Now lets say on the
same machine you are given a problem array of 1 million elements. So how
many clocks are you gonna consume, assuming all your 100 processors are
running in parallel.
Buddy, with parallel processors you can reduce total computation time at
most by a factor of number of processors you have (which will always be a
constant, no matter how big it is). It has nothing to do with time
complexity.
Thanks,
- Ravindra
On Fri, Oct 22, 2010 at 8:17 AM, Kishen Das wrote:
> Ok, if you look at the inner loop, it is -
>
> for ( j = i to j = 0 ) {
> sum[j] += A[ i]
> product[j] *= A [ i]
> }
>
> This is as good as executing -
> sum[i] = sum [ i ] + A[ i ] ---> ( 1 )
> sum[i-1]= sum[i-1]+ A[i] > ( 2 )
> --
> ---
> ---
> sum[0] = sum[ 0]+A[i] --> ( i )
>
> Each of these assignments doesn't have any dependency with other
> computations i.e.,
> ( 1 ) is independent of ( 2 ) to ( i ) and so does ( 2 ) , ( 3 ) ,
> ( i )
> and hence each of this can be assigned to a different processor.
> So, each of these statements( iterations) of the inner-loop j can be
> run in different processors, making it O(1).
>
> I am sorry, if people are still not getting my point !!!
> This is the best I can do !!!
>
> Kishen
>
> On Thu, Oct 21, 2010 at 9:08 AM, ligerdave wrote:
>
>> @Kishen
>>
>> I don't have much knowledge on parallel computation in OpenCL or CUDA.
>> Do you mean parallelised="not have to do the computation at all"?
>> did you mean without knowing the boundary of the inner loop which is
>> depended on the outer loop, the inner loop would be smart enough to
>> figure o
Re: [algogeeks] Re: Yahoo coding round question
@ravindara yeah this works perfect -- 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] Re: Yahoo coding round question
Here is a simple implementation. Complexity O(n). Please let me know if you
find any issues with this.
Assumptions as stated in original problem -
1- Required sub array is contiguous
2- Given array has only integers (+ve and -)
// Params are array arr, length of array n, given sum and product
void subarr( int* arr, int n, int sum, int prod)
{
int lb = 0; // Lower bound of sub array
int s = 0; // Temporary sum
int p = 1; // Temporary prod
int mod_p = (prod > 0) ? prod : (prod * -1); // |prod|
int min_p = mod_p * -1; // -|prod|
int i=0;
int found = 0;
for(i=0; i mod_p)
{
p /= arr[lb];
s -= arr[lb];
lb++;
}
if( s== sum && p == prod)
{
printf ("Sub array is from index %d to %d\n", lb, i);
found = 1;
break;
}
}
if(!found)
printf("No Matching sub-array found\n");
}
Thanks,
- Ravindra
On Mon, Oct 25, 2010 at 2:04 AM, Kishen Das wrote:
> @Ravindra, Ligerdave
> You guys are all right. But with GPUs, you can literally have thousands of
> threads running in parallel.
> Again, my aim was not to prove that my O(n ^ 2) algorithm is O ( n) on a
> single processor system.
> It was more towards making the members of this group to think on the lines
> of Parallelism.
> I long back agreed that the worst case for my algorithm is O(n^2 ) on
> single processor systems.
>
> The current problem is a variation of original subset problem which is
> NP-complete. ( http://en.wikipedia.org/wiki/Subset_sum_problem )
>
> I really appreciate a O(n) solution to this problem on a single-processor
> system.
>
> Kishen
>
> On Sun, Oct 24, 2010 at 1:50 PM, ravindra patel
> wrote:
>
>> >> It has nothing to do with time complexity.
>> My bad. Wrong choice of words. So in the PRAM model you can say the time
>> complexity is O(1), a pure theoretical concept. But the cost still remains
>> O(n), isn't it.
>>
>> I guess now onwards we'll have to specifically ask interviewers whether
>> they are asking for time complexity on scalar machine or on a parallel
>> machine. Unless specified otherwise, my assumption by default would be a
>> scalar one though.
>>
>> - Ravindra
>>
>>
>> On Sun, Oct 24, 2010 at 11:50 PM, ravindra patel <
>> ravindra.it...@gmail.com> wrote:
>>
>>> @ Kishen
>>> So lets say you have 100 parallel processors and you are given an array
>>> of 100 elements, then the loop will execute in 1 clock. Now lets say on the
>>> same machine you are given a problem array of 1 million elements. So how
>>> many clocks are you gonna consume, assuming all your 100 processors are
>>> running in parallel.
>>>
>>> Buddy, with parallel processors you can reduce total computation time at
>>> most by a factor of number of processors you have (which will always be a
>>> constant, no matter how big it is). It has nothing to do with time
>>> complexity.
>>>
>>> Thanks,
>>> - Ravindra
>>>
>>>
>>> On Fri, Oct 22, 2010 at 8:17 AM, Kishen Das wrote:
>>>
Ok, if you look at the inner loop, it is -
for ( j = i to j = 0 ) {
sum[j] += A[ i]
product[j] *= A [ i]
}
This is as good as executing -
sum[i] = sum [ i ] + A[ i ] ---> ( 1 )
sum[i-1]= sum[i-1]+ A[i] > ( 2 )
--
---
---
sum[0] = sum[ 0]+A[i] --> ( i )
Each of these assignments doesn't have any dependency with other
computations i.e.,
( 1 ) is independent of ( 2 ) to ( i ) and so does ( 2 ) , ( 3 ) ,
( i )
and hence each of this can be assigned to a different processor.
So, each of these statements( iterations) of the inner-loop j can be run
in different processors, making it O(1).
I am sorry, if people are still not getting my point !!!
This is the best I can do !!!
Kishen
On Thu, Oct 21, 2010 at 9:08 AM, ligerdave wrote:
> @Kishen
>
> I don't have much knowledge on parallel computation in OpenCL or CUDA.
> Do you mean parallelised="not have to do the computation at all"?
> did you mean without knowing the boundary of the inner loop which is
> depended on the outer loop, the inner loop would be smart enough to
> figure out the i and j?
>
> On Oct 20, 7:33 pm, Kishen Das wrote:
> > Well, looks like people are not understanding when I say "run a loop
> in
> > parallel "!!!
> >
> > Please look at some of the examples on Nvidia website on how
> computations
> > can be parallelised in OpenCL or CUDA.
> > And also some of the high level programming languages like Scala
> which is
> > also providing these parallel constructs.
> >
> > If you don't understand GPUs or not familiar with parallel constructs
> in
> > Java, then my algorithm will definitely look like O ( n ^ 2 ).
> >
> > Kishen
> >
> >
> >
> > On Wed, Oct 20, 2010 at 4:25 PM, ligerdave
> wrote:
> > > @Kishen
> > > as long as you have one for
Re: [algogeeks] Re: Yahoo coding round question
@Ravindra, Ligerdave
You guys are all right. But with GPUs, you can literally have thousands of
threads running in parallel.
Again, my aim was not to prove that my O(n ^ 2) algorithm is O ( n) on a
single processor system.
It was more towards making the members of this group to think on the lines
of Parallelism.
I long back agreed that the worst case for my algorithm is O(n^2 ) on single
processor systems.
The current problem is a variation of original subset problem which is
NP-complete. ( http://en.wikipedia.org/wiki/Subset_sum_problem )
I really appreciate a O(n) solution to this problem on a single-processor
system.
Kishen
On Sun, Oct 24, 2010 at 1:50 PM, ravindra patel wrote:
> >> It has nothing to do with time complexity.
> My bad. Wrong choice of words. So in the PRAM model you can say the time
> complexity is O(1), a pure theoretical concept. But the cost still remains
> O(n), isn't it.
>
> I guess now onwards we'll have to specifically ask interviewers whether
> they are asking for time complexity on scalar machine or on a parallel
> machine. Unless specified otherwise, my assumption by default would be a
> scalar one though.
>
> - Ravindra
>
>
> On Sun, Oct 24, 2010 at 11:50 PM, ravindra patel > wrote:
>
>> @ Kishen
>> So lets say you have 100 parallel processors and you are given an array of
>> 100 elements, then the loop will execute in 1 clock. Now lets say on the
>> same machine you are given a problem array of 1 million elements. So how
>> many clocks are you gonna consume, assuming all your 100 processors are
>> running in parallel.
>>
>> Buddy, with parallel processors you can reduce total computation time at
>> most by a factor of number of processors you have (which will always be a
>> constant, no matter how big it is). It has nothing to do with time
>> complexity.
>>
>> Thanks,
>> - Ravindra
>>
>>
>> On Fri, Oct 22, 2010 at 8:17 AM, Kishen Das wrote:
>>
>>> Ok, if you look at the inner loop, it is -
>>>
>>> for ( j = i to j = 0 ) {
>>> sum[j] += A[ i]
>>> product[j] *= A [ i]
>>> }
>>>
>>> This is as good as executing -
>>> sum[i] = sum [ i ] + A[ i ] ---> ( 1 )
>>> sum[i-1]= sum[i-1]+ A[i] > ( 2 )
>>> --
>>> ---
>>> ---
>>> sum[0] = sum[ 0]+A[i] --> ( i )
>>>
>>> Each of these assignments doesn't have any dependency with other
>>> computations i.e.,
>>> ( 1 ) is independent of ( 2 ) to ( i ) and so does ( 2 ) , ( 3 ) , (
>>> i )
>>> and hence each of this can be assigned to a different processor.
>>> So, each of these statements( iterations) of the inner-loop j can be run
>>> in different processors, making it O(1).
>>>
>>> I am sorry, if people are still not getting my point !!!
>>> This is the best I can do !!!
>>>
>>> Kishen
>>>
>>> On Thu, Oct 21, 2010 at 9:08 AM, ligerdave wrote:
>>>
@Kishen
I don't have much knowledge on parallel computation in OpenCL or CUDA.
Do you mean parallelised="not have to do the computation at all"?
did you mean without knowing the boundary of the inner loop which is
depended on the outer loop, the inner loop would be smart enough to
figure out the i and j?
On Oct 20, 7:33 pm, Kishen Das wrote:
> Well, looks like people are not understanding when I say "run a loop
in
> parallel "!!!
>
> Please look at some of the examples on Nvidia website on how
computations
> can be parallelised in OpenCL or CUDA.
> And also some of the high level programming languages like Scala which
is
> also providing these parallel constructs.
>
> If you don't understand GPUs or not familiar with parallel constructs
in
> Java, then my algorithm will definitely look like O ( n ^ 2 ).
>
> Kishen
>
>
>
> On Wed, Oct 20, 2010 at 4:25 PM, ligerdave
wrote:
> > @Kishen
> > as long as you have one for loop in another, you wont have O(n). it
> > will most likely run O(n^2)
>
> > On Oct 19, 7:41 pm, Kishen Das 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 ) {
> > > 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 <
> > >
Re: [algogeeks] Re: Yahoo coding round question
@saurabh koar : no it will give that sub array .. but "kishan das" solution
is good...
btw my code explanation is
A: 2 4 356
PRODUCT:2 8 24 120 720
SUM 2 6 9 14 20
suppose i want sum 8 and product 15
make hash table for product array (in hashtable store index of product in
array A)
suppose at index K..
devide A[i]/15if we get A[i]/ 15 in hash table it means (i+1) to k
contains product needed now check for sum ..check ( sum[k]-sum[i]==GIVEN
SUM) we get answer A(i+1 to k)
example
at k =3 120/15=8 will be present in hash table..get index of 8 in array
A..here 1 now compute SUM[3]-SUM[1]..which is 8 here as required so answer
is A(i+1 to k ) means A(2 to 3) ={3,5}
--
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] Re: Yahoo coding round question
@ravindra
agree!
On Oct 24, 2:20 pm, ravindra patel wrote:
> @ Kishen
> So lets say you have 100 parallel processors and you are given an array of
> 100 elements, then the loop will execute in 1 clock. Now lets say on the
> same machine you are given a problem array of 1 million elements. So how
> many clocks are you gonna consume, assuming all your 100 processors are
> running in parallel.
>
> Buddy, with parallel processors you can reduce total computation time at
> most by a factor of number of processors you have (which will always be a
> constant, no matter how big it is). It has nothing to do with time
> complexity.
>
> Thanks,
> - Ravindra
>
>
>
> On Fri, Oct 22, 2010 at 8:17 AM, Kishen Das wrote:
> > Ok, if you look at the inner loop, it is -
>
> > for ( j = i to j = 0 ) {
> > sum[j] += A[ i]
> > product[j] *= A [ i]
> > }
>
> > This is as good as executing -
> > sum[i] = sum [ i ] + A[ i ] ---> ( 1 )
> > sum[i-1]= sum[i-1]+ A[i] > ( 2 )
> > --
> > ---
> > ---
> > sum[0] = sum[ 0]+A[i] --> ( i )
>
> > Each of these assignments doesn't have any dependency with other
> > computations i.e.,
> > ( 1 ) is independent of ( 2 ) to ( i ) and so does ( 2 ) , ( 3 ) , ( i
> > )
> > and hence each of this can be assigned to a different processor.
> > So, each of these statements( iterations) of the inner-loop j can be run in
> > different processors, making it O(1).
>
> > I am sorry, if people are still not getting my point !!!
> > This is the best I can do !!!
>
> > Kishen
>
> > On Thu, Oct 21, 2010 at 9:08 AM, ligerdave wrote:
>
> >> @Kishen
>
> >> I don't have much knowledge on parallel computation in OpenCL or CUDA.
> >> Do you mean parallelised="not have to do the computation at all"?
> >> did you mean without knowing the boundary of the inner loop which is
> >> depended on the outer loop, the inner loop would be smart enough to
> >> figure out the i and j?
>
> >> On Oct 20, 7:33 pm, Kishen Das wrote:
> >> > Well, looks like people are not understanding when I say "run a loop in
> >> > parallel "!!!
>
> >> > Please look at some of the examples on Nvidia website on how
> >> computations
> >> > can be parallelised in OpenCL or CUDA.
> >> > And also some of the high level programming languages like Scala which
> >> is
> >> > also providing these parallel constructs.
>
> >> > If you don't understand GPUs or not familiar with parallel constructs in
> >> > Java, then my algorithm will definitely look like O ( n ^ 2 ).
>
> >> > Kishen
>
> >> > On Wed, Oct 20, 2010 at 4:25 PM, ligerdave
> >> wrote:
> >> > > @Kishen
> >> > > as long as you have one for loop in another, you wont have O(n). it
> >> > > will most likely run O(n^2)
>
> >> > > On Oct 19, 7:41 pm, Kishen Das 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 ) {
> >> > > > 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.com >> > > > >> .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 >> > > > > .com>
> >>
> >> > >
> >> > > > > .
> >> > > > >
Re: [algogeeks] Re: Yahoo coding round question
@Mohit: What I understand that in your solution the sum and product array contains the sum and products of contiguous sub-array starting from 0 to i (index of array A). What happens when the expected sub array starts form an index other than 0? -- 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] Re: Yahoo coding round question
>> It has nothing to do with time complexity.
My bad. Wrong choice of words. So in the PRAM model you can say the time
complexity is O(1), a pure theoretical concept. But the cost still remains
O(n), isn't it.
I guess now onwards we'll have to specifically ask interviewers whether they
are asking for time complexity on scalar machine or on a parallel machine.
Unless specified otherwise, my assumption by default would be a scalar one
though.
- Ravindra
On Sun, Oct 24, 2010 at 11:50 PM, ravindra patel
wrote:
> @ Kishen
> So lets say you have 100 parallel processors and you are given an array of
> 100 elements, then the loop will execute in 1 clock. Now lets say on the
> same machine you are given a problem array of 1 million elements. So how
> many clocks are you gonna consume, assuming all your 100 processors are
> running in parallel.
>
> Buddy, with parallel processors you can reduce total computation time at
> most by a factor of number of processors you have (which will always be a
> constant, no matter how big it is). It has nothing to do with time
> complexity.
>
> Thanks,
> - Ravindra
>
>
> On Fri, Oct 22, 2010 at 8:17 AM, Kishen Das wrote:
>
>> Ok, if you look at the inner loop, it is -
>>
>> for ( j = i to j = 0 ) {
>> sum[j] += A[ i]
>> product[j] *= A [ i]
>> }
>>
>> This is as good as executing -
>> sum[i] = sum [ i ] + A[ i ] ---> ( 1 )
>> sum[i-1]= sum[i-1]+ A[i] > ( 2 )
>> --
>> ---
>> ---
>> sum[0] = sum[ 0]+A[i] --> ( i )
>>
>> Each of these assignments doesn't have any dependency with other
>> computations i.e.,
>> ( 1 ) is independent of ( 2 ) to ( i ) and so does ( 2 ) , ( 3 ) , (
>> i )
>> and hence each of this can be assigned to a different processor.
>> So, each of these statements( iterations) of the inner-loop j can be run
>> in different processors, making it O(1).
>>
>> I am sorry, if people are still not getting my point !!!
>> This is the best I can do !!!
>>
>> Kishen
>>
>> On Thu, Oct 21, 2010 at 9:08 AM, ligerdave wrote:
>>
>>> @Kishen
>>>
>>> I don't have much knowledge on parallel computation in OpenCL or CUDA.
>>> Do you mean parallelised="not have to do the computation at all"?
>>> did you mean without knowing the boundary of the inner loop which is
>>> depended on the outer loop, the inner loop would be smart enough to
>>> figure out the i and j?
>>>
>>> On Oct 20, 7:33 pm, Kishen Das wrote:
>>> > Well, looks like people are not understanding when I say "run a loop in
>>> > parallel "!!!
>>> >
>>> > Please look at some of the examples on Nvidia website on how
>>> computations
>>> > can be parallelised in OpenCL or CUDA.
>>> > And also some of the high level programming languages like Scala which
>>> is
>>> > also providing these parallel constructs.
>>> >
>>> > If you don't understand GPUs or not familiar with parallel constructs
>>> in
>>> > Java, then my algorithm will definitely look like O ( n ^ 2 ).
>>> >
>>> > Kishen
>>> >
>>> >
>>> >
>>> > On Wed, Oct 20, 2010 at 4:25 PM, ligerdave
>>> wrote:
>>> > > @Kishen
>>> > > as long as you have one for loop in another, you wont have O(n). it
>>> > > will most likely run O(n^2)
>>> >
>>> > > On Oct 19, 7:41 pm, Kishen Das 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 ) {
>>> > > > 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 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.
>>> >
>>> > > > > --
>>> > > > > ABHISHEK KUMAR SINGH
>>> > > > > BTECH (INFORMATION TECHNOLOGY)
>>> > > >
Re: [algogeeks] Re: Yahoo coding round question
@ Kishen
So lets say you have 100 parallel processors and you are given an array of
100 elements, then the loop will execute in 1 clock. Now lets say on the
same machine you are given a problem array of 1 million elements. So how
many clocks are you gonna consume, assuming all your 100 processors are
running in parallel.
Buddy, with parallel processors you can reduce total computation time at
most by a factor of number of processors you have (which will always be a
constant, no matter how big it is). It has nothing to do with time
complexity.
Thanks,
- Ravindra
On Fri, Oct 22, 2010 at 8:17 AM, Kishen Das wrote:
> Ok, if you look at the inner loop, it is -
>
> for ( j = i to j = 0 ) {
> sum[j] += A[ i]
> product[j] *= A [ i]
> }
>
> This is as good as executing -
> sum[i] = sum [ i ] + A[ i ] ---> ( 1 )
> sum[i-1]= sum[i-1]+ A[i] > ( 2 )
> --
> ---
> ---
> sum[0] = sum[ 0]+A[i] --> ( i )
>
> Each of these assignments doesn't have any dependency with other
> computations i.e.,
> ( 1 ) is independent of ( 2 ) to ( i ) and so does ( 2 ) , ( 3 ) , ( i
> )
> and hence each of this can be assigned to a different processor.
> So, each of these statements( iterations) of the inner-loop j can be run in
> different processors, making it O(1).
>
> I am sorry, if people are still not getting my point !!!
> This is the best I can do !!!
>
> Kishen
>
> On Thu, Oct 21, 2010 at 9:08 AM, ligerdave wrote:
>
>> @Kishen
>>
>> I don't have much knowledge on parallel computation in OpenCL or CUDA.
>> Do you mean parallelised="not have to do the computation at all"?
>> did you mean without knowing the boundary of the inner loop which is
>> depended on the outer loop, the inner loop would be smart enough to
>> figure out the i and j?
>>
>> On Oct 20, 7:33 pm, Kishen Das wrote:
>> > Well, looks like people are not understanding when I say "run a loop in
>> > parallel "!!!
>> >
>> > Please look at some of the examples on Nvidia website on how
>> computations
>> > can be parallelised in OpenCL or CUDA.
>> > And also some of the high level programming languages like Scala which
>> is
>> > also providing these parallel constructs.
>> >
>> > If you don't understand GPUs or not familiar with parallel constructs in
>> > Java, then my algorithm will definitely look like O ( n ^ 2 ).
>> >
>> > Kishen
>> >
>> >
>> >
>> > On Wed, Oct 20, 2010 at 4:25 PM, ligerdave
>> wrote:
>> > > @Kishen
>> > > as long as you have one for loop in another, you wont have O(n). it
>> > > will most likely run O(n^2)
>> >
>> > > On Oct 19, 7:41 pm, Kishen Das 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 ) {
>> > > > 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.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.
>> >
>> > > --
>> > > You received this message because you are subscribed to the Google
>> Groups
>> > > "Algorithm Geeks" group.
>> > > To post to this group, send email to algog
[algogeeks] Re: Yahoo coding round question
@Kishen
i think parallel computation means when you have two tasks, instead
having only one person working on both, you have two persons working
simultaneously. however, that doesnt mean you dont have to do the job
right? the problem isn't in the inner loop.
when you have one loop inside of another loop, you general would have
n^2. again, we are talking about bigO, which means the worst time
On Oct 21, 10:47 pm, Kishen Das wrote:
> Ok, if you look at the inner loop, it is -
>
> for ( j = i to j = 0 ) {
> sum[j] += A[ i]
> product[j] *= A [ i]
>
> }
>
> This is as good as executing -
> sum[i] = sum [ i ] + A[ i ] ---> ( 1 )
> sum[i-1]= sum[i-1]+ A[i] > ( 2 )
> --
> ---
> ---
> sum[0] = sum[ 0]+A[i] --> ( i )
>
> Each of these assignments doesn't have any dependency with other
> computations i.e.,
> ( 1 ) is independent of ( 2 ) to ( i ) and so does ( 2 ) , ( 3 ) , ( i
> )
> and hence each of this can be assigned to a different processor.
> So, each of these statements( iterations) of the inner-loop j can be run in
> different processors, making it O(1).
>
> I am sorry, if people are still not getting my point !!!
> This is the best I can do !!!
>
> Kishen
>
>
>
>
>
>
>
> On Thu, Oct 21, 2010 at 9:08 AM, ligerdave wrote:
> > @Kishen
>
> > I don't have much knowledge on parallel computation in OpenCL or CUDA.
> > Do you mean parallelised="not have to do the computation at all"?
> > did you mean without knowing the boundary of the inner loop which is
> > depended on the outer loop, the inner loop would be smart enough to
> > figure out the i and j?
>
> > On Oct 20, 7:33 pm, Kishen Das wrote:
> > > Well, looks like people are not understanding when I say "run a loop in
> > > parallel "!!!
>
> > > Please look at some of the examples on Nvidia website on how computations
> > > can be parallelised in OpenCL or CUDA.
> > > And also some of the high level programming languages like Scala which is
> > > also providing these parallel constructs.
>
> > > If you don't understand GPUs or not familiar with parallel constructs in
> > > Java, then my algorithm will definitely look like O ( n ^ 2 ).
>
> > > Kishen
>
> > > On Wed, Oct 20, 2010 at 4:25 PM, ligerdave wrote:
> > > > @Kishen
> > > > as long as you have one for loop in another, you wont have O(n). it
> > > > will most likely run O(n^2)
>
> > > > On Oct 19, 7:41 pm, Kishen Das 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 ) {
> > > > > 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.com > > > > >> .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 > > > > > .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 > > > .com>
>
Re: [algogeeks] Re: Yahoo coding round question
Ok, if you look at the inner loop, it is -
for ( j = i to j = 0 ) {
sum[j] += A[ i]
product[j] *= A [ i]
}
This is as good as executing -
sum[i] = sum [ i ] + A[ i ] ---> ( 1 )
sum[i-1]= sum[i-1]+ A[i] > ( 2 )
--
---
---
sum[0] = sum[ 0]+A[i] --> ( i )
Each of these assignments doesn't have any dependency with other
computations i.e.,
( 1 ) is independent of ( 2 ) to ( i ) and so does ( 2 ) , ( 3 ) , ( i
)
and hence each of this can be assigned to a different processor.
So, each of these statements( iterations) of the inner-loop j can be run in
different processors, making it O(1).
I am sorry, if people are still not getting my point !!!
This is the best I can do !!!
Kishen
On Thu, Oct 21, 2010 at 9:08 AM, ligerdave wrote:
> @Kishen
>
> I don't have much knowledge on parallel computation in OpenCL or CUDA.
> Do you mean parallelised="not have to do the computation at all"?
> did you mean without knowing the boundary of the inner loop which is
> depended on the outer loop, the inner loop would be smart enough to
> figure out the i and j?
>
> On Oct 20, 7:33 pm, Kishen Das wrote:
> > Well, looks like people are not understanding when I say "run a loop in
> > parallel "!!!
> >
> > Please look at some of the examples on Nvidia website on how computations
> > can be parallelised in OpenCL or CUDA.
> > And also some of the high level programming languages like Scala which is
> > also providing these parallel constructs.
> >
> > If you don't understand GPUs or not familiar with parallel constructs in
> > Java, then my algorithm will definitely look like O ( n ^ 2 ).
> >
> > Kishen
> >
> >
> >
> > On Wed, Oct 20, 2010 at 4:25 PM, ligerdave wrote:
> > > @Kishen
> > > as long as you have one for loop in another, you wont have O(n). it
> > > will most likely run O(n^2)
> >
> > > On Oct 19, 7:41 pm, Kishen Das 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 ) {
> > > > 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.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.
> >
> > > --
> > > 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.
>
>
--
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
[algogeeks] Re: Yahoo coding round question
@Kishen
I don't have much knowledge on parallel computation in OpenCL or CUDA.
Do you mean parallelised="not have to do the computation at all"?
did you mean without knowing the boundary of the inner loop which is
depended on the outer loop, the inner loop would be smart enough to
figure out the i and j?
On Oct 20, 7:33 pm, Kishen Das wrote:
> Well, looks like people are not understanding when I say "run a loop in
> parallel "!!!
>
> Please look at some of the examples on Nvidia website on how computations
> can be parallelised in OpenCL or CUDA.
> And also some of the high level programming languages like Scala which is
> also providing these parallel constructs.
>
> If you don't understand GPUs or not familiar with parallel constructs in
> Java, then my algorithm will definitely look like O ( n ^ 2 ).
>
> Kishen
>
>
>
> On Wed, Oct 20, 2010 at 4:25 PM, ligerdave wrote:
> > @Kishen
> > as long as you have one for loop in another, you wont have O(n). it
> > will most likely run O(n^2)
>
> > On Oct 19, 7:41 pm, Kishen Das 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 ) {
> > > 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 > >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.com > > >> .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 > > > .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 > .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] Re: Yahoo coding round question
Well, looks like people are not understanding when I say "run a loop in
parallel "!!!
Please look at some of the examples on Nvidia website on how computations
can be parallelised in OpenCL or CUDA.
And also some of the high level programming languages like Scala which is
also providing these parallel constructs.
If you don't understand GPUs or not familiar with parallel constructs in
Java, then my algorithm will definitely look like O ( n ^ 2 ).
Kishen
On Wed, Oct 20, 2010 at 4:25 PM, ligerdave wrote:
> @Kishen
> as long as you have one for loop in another, you wont have O(n). it
> will most likely run O(n^2)
>
> On Oct 19, 7:41 pm, Kishen Das 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 ) {
> > 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 >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.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.
>
> --
> 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.
[algogeeks] Re: Yahoo coding round question
@Kishen
as long as you have one for loop in another, you wont have O(n). it
will most likely run O(n^2)
On Oct 19, 7:41 pm, Kishen Das 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 ) {
> 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
> 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.com >> .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 > .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] Re: Yahoo coding round question
i wanna get a clear picture of this before start. when you say min length of contiguous sub of an array let's say array A=[3,1,2,3,4,5], N=6 are below both good solutions? A[0] to A[m] where m<=N A[i] to A[m] where i<=m m<=N On Oct 19, 3:58 am, Abhishek Kumar Singh 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Yahoo coding round question
@W Karas Can you please give an example and explain your approach. Anurag Sharma On Tue, May 18, 2010 at 12:17 AM, W Karas wrote: > One (space-intensive) idea: > > Re-represent each string as a set of pairs (character, position of > character). Then sort each set of pairs by character. Then find > corresponding sequences in the sorted lists of pairs, where the > character and the difference between position is the same from pair to > pair in the sequence. Then narrow down the sequences to those that > actually are substrings of adjacent characters and choose the longest. > > On May 8, 5:00 am, Jitendra Kushwaha 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.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] Re: Yahoo coding round question
One (space-intensive) idea: Re-represent each string as a set of pairs (character, position of character). Then sort each set of pairs by character. Then find corresponding sequences in the sorted lists of pairs, where the character and the difference between position is the same from pair to pair in the sequence. Then narrow down the sequences to those that actually are substrings of adjacent characters and choose the longest. On May 8, 5:00 am, Jitendra Kushwaha 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
