Re: [algogeeks] Finding parallel edges in graph
What will be the input for the graph? Kishen On Thu, Oct 21, 2010 at 5:22 AM, Algorithimist yogi15...@gmail.com wrote: Design an algorithm to determine whether a graph has any parallel edges in time proportional to E + V. -- 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] Re: 10 most repeating words
MapReduce is the best option . For the word count its explained here - http://en.wikipedia.org/wiki/MapReduce Interesting thing is that the Map step can easily be made parallel. Once again I request the members of this group to go through all the parallel constructs. ( Parallel sorting, Parallel collections, etc ) Its cool to optimize sequential programs, but with GPUs and ever increasing cores, you should start thinking in terms of parallelizing your code. Kishen On Fri, Oct 22, 2010 at 9:24 AM, ligerdave david.c...@gmail.com wrote: for a large file, you probably would want to use external sort. kinda like a map-reduce concept. it's actually how sortuniq kinda stuff work in unix/linux when you try to find some TOP X again, we are talking about the memory might not hold the entire file On Oct 21, 9:35 am, Vinay... vinumars...@gmail.com wrote: how do u find 10 most repeating words on a large file containing words in most efficient way...if it can also be done using heapsort plz post ur answers.. -- 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] 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 ravindra.it...@gmail.comwrote:
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 kishen@gmail.com 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 david.c...@gmail.com 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 kishen@gmail.com 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 david.c...@gmail.com
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 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 ) {
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
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 david.c...@gmail.com 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 kishen@gmail.com 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 david.c...@gmail.com 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 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 ) {
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
algogeeks%2bunsubscr...@googlegroups .com
algogeeks%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
algogeeks%2bunsubscr...@googlegroups .com
algogeeks%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
algogeeks%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
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] 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 david.c...@gmail.com 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 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 ) {
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
algogeeks%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
algogeeks%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.
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
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] Re: P ! = NP
http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/ Looks like there are serious flaws with this proof but it can produce other interesting results. http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/ Kishen On Sat, Aug 14, 2010 at 7:30 AM, LawCounsels lawcouns...@aol.com wrote: On 11 Aug, 23:54, Kishen Das kishen@gmail.com wrote: http://www.telegraph.co.uk/science/science-news/7938238/Computer-scie... Check out this cool news. Kishen On 10 Aug, 06:50, Niels Fröhling spamt...@adsignum.com wrote: Up to date reactions, comments of the community/researchers (summary): http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%E... Deolalikar may possibly have proven the lesser significant of either P! =NP (not the more 'unthinkable' P=NP) ... it appears New Generation Lossless Data Representations likely point the way forward to prove the 'converse' P=NP feasible ! -- 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] How will you find the page with most incoming links from billions of web-pages
:-) that was funny. I think you can take a look at the concepts of web-page ranking algorithms - http://www.cpccci.com/academics/surveypagerank.htm http://www.cpccci.com/academics/surveypagerank.htmKishen On Thu, Aug 12, 2010 at 1:33 AM, thiru pujari thiru.puj...@gmail.comwrote: i found this website from my friend On Thu, Aug 12, 2010 at 11:41 AM, vijay auvija...@gmail.com wrote: How will you find the page with most incoming links from billions of web-pages -- 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. -- UR'S THIRU -- 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] P ! = NP
http://www.telegraph.co.uk/science/science-news/7938238/Computer-scientist-Vinay-Deolalikar-claims-to-have-solved-maths-riddle-of-P-vs-NP.html Check out this cool news. Kishen -- 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] P ! = NP
Thats the scary part. Some MIT Professor has announced additional 200 thousand dollars, if the proof is correct. He will surely get a turing, if the proof is correct. Will be second Indian after Raj Reddy to achieve this. Kishen On Wed, Aug 11, 2010 at 7:58 PM, Varun Nagpal varun.nagp...@gmail.comwrote: Yeah,,,...lets hope the next turing goes to this Indian. Its still being verified. On Thu, Aug 12, 2010 at 12:54 AM, Kishen Das kishen@gmail.com wrote: http://www.telegraph.co.uk/science/science-news/7938238/Computer-scientist-Vinay-Deolalikar-claims-to-have-solved-maths-riddle-of-P-vs-NP.html Check out this cool news. Kishen -- 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] ACTIVATION OF WINDOWS 7
May be if you want to discuss what sort of algorithms MS might be using to generate the serial key, then this is the right place :D Kishen On Sun, Jun 20, 2010 at 4:16 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: So, is this the place for that? And apart from that, it is illegal to discuss about this on public threads. (if you don't know, this thread is public) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sun, Jun 20, 2010 at 2:42 PM, vishard sankhyan er.vish...@gmail.comwrote: HI ANY ONE HELP OUT I WANT TO ACTIVATE MY WINDOWS 7.. -- 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] infy color balls
Answer is k! * k^(n-k). You can select k number of balls in K! ways and then rest of (n-k) balls in k ways. This way you are ensuring that you have all k color balls and n number of balls in total. - Kishen Das On Fri, Apr 30, 2010 at 6:04 AM, Ashish Mishra amishra@gmail.comwrote: One of my friend ask me this n i am bad in P C (will love if smone can provide me a link to learn it though) nyways prob is: there are infy color balls of k different color you are allowed to pick n balls out of those infy(infinite) balls cond is : you must have all k color balls with u obviously kn Question is how many possibilities for selection you have ? Thanks Ashish -- 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] a google question
Basically the index of ( a + b) in the final array will be ceil(( index of a
+ index of b )/2).
Also if there is a clash of indices you just have to compare the values at
those indices and adjust them.
I have run my concept with below two arrays and it works !!!
Arary A: 1 2 3 4 5 6
Array B: 2 3 5 6 8 9
addition of indices 84511611
addition of values (2+9) ( 1+5) (4+2) (6+8) ( 3+3) ( 5 + 9)
values: 11 6 6 14 9 14
Added indices: 4 5 6 8 11 11 ( These are not sorted indices, you will
know the indices of values in the final array right away after looking at
the indices of a and b )
indices/2: 2 3 3 4 6 6
corresponding final values6 6 6 11 14 14
- Kishen Das
On Fri, Apr 30, 2010 at 7:05 AM, divya sweetdivya@gmail.com wrote:
Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's
say they are decreasingly sorted), we define a set S = {(a,b) | a \in
A
and b \in B}. Obviously there are n^2 elements in S. The value of such
a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
from S with largest values. The tricky part is that we need an O(n)
algorithm.
--
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.
