Re: [algogeeks] BST Question
oh ya thanks now i got it On Sun, Oct 24, 2010 at 9:54 AM, preetika tyagi preetikaty...@gmail.comwrote: @Praveen- In this case, we will not ignore the right subtree of the root (-10, which is less than zero) while traversing the tree. On Sat, Oct 23, 2010 at 9:06 PM, Praveen Baskar praveen200...@gmail.comwrote: i think it is possible nishaanth please do take a look at this example -10 /\ -11 8 /\ -5 10 -5 is greater than -10 On Sat, Oct 23, 2010 at 11:19 PM, nishaanth nishaant...@gmail.comwrote: @Praveenit is not possible..in a BST *all the nodes* on the right subtree are greater than the node :) On Sat, Oct 16, 2010 at 3:26 PM, Praveen Baskar praveen200...@gmail.com wrote: @nishaanth: wat if the left child of the right node has a negative value On Thu, Oct 14, 2010 at 11:12 AM, nishaanth nishaant...@gmail.comwrote: Just see the value of the node at every point, if it is greater than zero dont recurse the right sub-tree, as simple as it is.print the node u inspected if it is less than zero. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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. -- By B. Praveen -- 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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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. -- By B. Praveen -- 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. -- By B. Praveen -- 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: Algorithm to find whether any 3point on the same line
@Ravindra: Can you explain the algorithm for step 3 in more detail? I don't yet see how you do it in O(n^2), since it seems to me that comparing one A[i,j] to all the A[j,k] is already O(n^2). What am I missing? Dave On Oct 24, 12:05 am, ravindra patel ravindra.it...@gmail.com wrote: Can be done in O(n^2) time using the slope as people suggested above. 1- Sort the points in increasing order of x cord. O(nlogn) 2- prepare a n*n matrix A where A[i,j] = slope( point(i), point(j) ) - O(n^2) [Note that point i and j are sorted in increasing order of x] 3- find a pair of A[i,j] and A[j,k] with same slope. [Can be done in O(n^2)] Thanks, - Ravindra On Sun, Oct 24, 2010 at 10:11 AM, Dave dave_and_da...@juno.com wrote: @Preetika: Then you have to look for duplicates in an array of n(n-1)/ 2 real numbers. I think this takes the complexity above O(n^2). Dave On Oct 23, 10:54 pm, preetika tyagi preetikaty...@gmail.com wrote: You have to scan every pair of points only once to get the value of 'm' and 'a', so the time complexity would be O(n^2). On Sat, Oct 23, 2010 at 6:22 PM, Meng Yan mengyan.fu...@gmail.com wrote: there are (n*(n-1))/2pairs of points. I think if we use your method, the time complexity should be O(n^4). Is it possible to put all points into k different domain and using T(n)=T(n/k)+f(n) to solve this problem? On Sat, Oct 23, 2010 at 7:51 PM, preetika tyagi preetikaty...@gmail.comwrote: Is there any specific need to use recursion? One alternate is to find slope and constant (m and c) for every pair of points and same value of m c will specify the points on the same line. Time complexity is O(n*n). On Sat, Oct 23, 2010 at 4:31 PM, Meng Yan mengyan.fu...@gmail.com wrote: Given n point on the plane, find out whether any 3point on the same line. How to use recursion to solve the problem? Could you help me find the algorithm and give the time complexity? Bests, Claire -- 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 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.-Hide quoted text - - Show quoted text - -- 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.- Hide quoted text - - Show quoted text - -- 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: Algorithm to find whether any 3point on the same line
We can do the following in 2-D plane where the pints are given in the form of (x.y). For each selection of three points do the following: Find the area of the triangle of the three points. Let it be A. If A is zero then Print Existence of Co-linear points Break. This can be achieved in C(n,3) steps so the time complexity is n(n-1) (n-2)/6 = O(n^3). -- 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: BST Question
The suggestion will work if the root is known to have entry equal to zero. (Even it is less than 0, there is a chance that a negative an reside in right sub-tree whose value is 0 but greater than the negative value of the root). If the entry of the root is zero then we can do the inorder traversal. Also if the BST is rooted tree (say there is a special mark for identifying the root) then we can identify the root and use this to terminate the algorithm after printing the result. -- 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: Binary Tree
We can do the following. We associate a variable with each of the node. let it be called level. We now do BFS on the tree. Whenever we visit a node we do the following: node.level = blackNeigbor.level + 1. Now we again do a BFS to find the number of nodes in each level. -- 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: how would you find the integer pairs which sum to m in o(n) time complexity
We can follow an algorithm described below. Set found:= FALSE For each number n belong to array A.and until found != TRUE For each number k in A not equal to n, do: if k+n == m then output The pairs are n and k Set found:=TRUE. Break. The running time will be of O(n^2). -- 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: Finding parallel edges in graph
Consider the following adjacency-matrix representation of a graph, R(V,E). Let there be n number of vertices. So we create n*n matrix G[1..n] [1..n]. Initially set G[i][j]=0 for all 1= i,j =n. This operation will take O(V). For each edge e of R let (a,b) be the adjacent vertices, set G[a] [b] :=G[a][b]+1. This will take O(E). Set parallel:= FALSE For i=1 to n and until parallel == FALSE, do: For j=1 to n, do: if G[i][j]1, then Print Parallel Edges detected Set parallel:= TRUE. Break. -- 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: Algorithm to find whether any 3point on the same line
for the 3th step, for i=1 to n for j=i+1 to n for k=j+1 to n compare A[i,j] and A[j,k] if A[i,j]==A[j,k] find i,j,k are collinear. so we should need O(n^3), is it right? On Sun, Oct 24, 2010 at 1:05 AM, ravindra patel ravindra.it...@gmail.comwrote: Can be done in O(n^2) time using the slope as people suggested above. 1- Sort the points in increasing order of x cord. O(nlogn) 2- prepare a n*n matrix A where A[i,j] = slope( point(i), point(j) ) - O(n^2) [Note that point i and j are sorted in increasing order of x] 3- find a pair of A[i,j] and A[j,k] with same slope. [Can be done in O(n^2)] Thanks, - Ravindra On Sun, Oct 24, 2010 at 10:11 AM, Dave dave_and_da...@juno.com wrote: @Preetika: Then you have to look for duplicates in an array of n(n-1)/ 2 real numbers. I think this takes the complexity above O(n^2). Dave On Oct 23, 10:54 pm, preetika tyagi preetikaty...@gmail.com wrote: You have to scan every pair of points only once to get the value of 'm' and 'a', so the time complexity would be O(n^2). On Sat, Oct 23, 2010 at 6:22 PM, Meng Yan mengyan.fu...@gmail.com wrote: there are (n*(n-1))/2pairs of points. I think if we use your method, the time complexity should be O(n^4). Is it possible to put all points into k different domain and using T(n)=T(n/k)+f(n) to solve this problem? On Sat, Oct 23, 2010 at 7:51 PM, preetika tyagi preetikaty...@gmail.comwrote: Is there any specific need to use recursion? One alternate is to find slope and constant (m and c) for every pair of points and same value of m c will specify the points on the same line. Time complexity is O(n*n). On Sat, Oct 23, 2010 at 4:31 PM, Meng Yan mengyan.fu...@gmail.com wrote: Given n point on the plane, find out whether any 3point on the same line. How to use recursion to solve the problem? Could you help me find the algorithm and give the time complexity? Bests, Claire -- 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 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.- Hide quoted text - - Show quoted text - -- 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: Algorithm to find whether any 3point on the same line
@Dave I was wrong. It can't be done in O(n^2) time. The best we can do is sort each row like you suggested in your other post. That will still be O((n^2)logn). Thanks, - Ravindra On Sun, Oct 24, 2010 at 7:06 PM, Meng Yan mengyan.fu...@gmail.com wrote: for the 3th step, for i=1 to n for j=i+1 to n for k=j+1 to n compare A[i,j] and A[j,k] if A[i,j]==A[j,k] find i,j,k are collinear. so we should need O(n^3), is it right? On Sun, Oct 24, 2010 at 1:05 AM, ravindra patel ravindra.it...@gmail.comwrote: Can be done in O(n^2) time using the slope as people suggested above. 1- Sort the points in increasing order of x cord. O(nlogn) 2- prepare a n*n matrix A where A[i,j] = slope( point(i), point(j) ) - O(n^2) [Note that point i and j are sorted in increasing order of x] 3- find a pair of A[i,j] and A[j,k] with same slope. [Can be done in O(n^2)] Thanks, - Ravindra On Sun, Oct 24, 2010 at 10:11 AM, Dave dave_and_da...@juno.com wrote: @Preetika: Then you have to look for duplicates in an array of n(n-1)/ 2 real numbers. I think this takes the complexity above O(n^2). Dave On Oct 23, 10:54 pm, preetika tyagi preetikaty...@gmail.com wrote: You have to scan every pair of points only once to get the value of 'm' and 'a', so the time complexity would be O(n^2). On Sat, Oct 23, 2010 at 6:22 PM, Meng Yan mengyan.fu...@gmail.com wrote: there are (n*(n-1))/2pairs of points. I think if we use your method, the time complexity should be O(n^4). Is it possible to put all points into k different domain and using T(n)=T(n/k)+f(n) to solve this problem? On Sat, Oct 23, 2010 at 7:51 PM, preetika tyagi preetikaty...@gmail.comwrote: Is there any specific need to use recursion? One alternate is to find slope and constant (m and c) for every pair of points and same value of m c will specify the points on the same line. Time complexity is O(n*n). On Sat, Oct 23, 2010 at 4:31 PM, Meng Yan mengyan.fu...@gmail.com wrote: Given n point on the plane, find out whether any 3point on the same line. How to use recursion to solve the problem? Could you help me find the algorithm and give the time complexity? Bests, Claire -- 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 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.- Hide quoted text - - Show quoted text - -- 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.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
[algogeeks] Re: 10 most repeating words
@Dave I hear ya. Im just saying in general, you would wanna have an algorithm for all cases. of coz, in this case, if the RAM isn't a consideration and heapsort is what @Vinay wants, i guess we are coming up w/ one like that. again, in general, you don't wanna have one version of program for king james and another for something that's more right? btw, do you have any new clue on the nth largest sum of two arrays? i realized the solution i gave wasn't working for all cases. im on the right track i think. however, there is something must be fixed and im scratching my head now. :) let me know man! On Oct 22, 11:19 pm, Dave dave_and_da...@juno.com wrote: @Ligerdave: Hey, the King James version of the Bible is only about 600,000 words. I use the Bible as an example only because it is a fairly large book. Maybe we are talking 10 megabytes to store the whole thing, seeing that there are some long words such as Maher- shalal-hash-baz, a name that occurs in Isaiah 8:3. Ten megabytes hardly seems large, when compared to the 4 or 8 gigabytes or more of RAM on many computers. Besides, you don't have to keep all of the text in memory, but only the distinct words and an integer count of the number of occurrences. For the King James bible, this is less than 5,000 words, so we're talking a pretty minimal amount of memory. A hash table might work fine for this, or build a balanced binary tree of the words. After you have scanned all of the input text and determined the number of occurrences of each word, it is fairly easy to scan the word counts and pick out the ten largest. Dave On Oct 22, 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..- Hide quoted text - - Show quoted text - -- 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
@ 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...@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
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
ravindra.it...@gmail.comwrote:
@ 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 algogeeks@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
Re: [algogeeks] Re: how would you find the integer pairs which sum to m in o(n) time complexity
I think we can sort the elements first and then start scanning from both ends of the array. All the pairs can be found this way and the complexity will be O(nlogn). On Sun, Oct 24, 2010 at 6:08 AM, Avik Mitra tutai...@gmail.com wrote: We can follow an algorithm described below. Set found:= FALSE For each number n belong to array A.and until found != TRUE For each number k in A not equal to n, do: if k+n == m then output The pairs are n and k Set found:=TRUE. Break. The running time will be of O(n^2). -- 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
@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.
[algogeeks] Re: Yahoo coding round question
@ravindra
agree!
On Oct 24, 2:20 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...@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
[algogeeks] Re: 10 most repeating words
The biggest weakness of the trie is the amount of space it wastes - chances are there will be runs of characters with a word only at the end, meaning a bunch of extra levels of the tree that aren't needed. The PATRICIA trie, or radix trie, attempts to address this by allowing the 'decision' at each note to be on something other than the first character, so each node stores an offset and the branch options (e.g. if the letter in position 5 is A, go down this branch) On Oct 23, 9:13 pm, Chi c...@linuxdna.com wrote: I've written a kart-trie in php. You can easily extend yourself the payload to count the word frequency. http://sourceforge.net/projects/kart-trie After you build your dictionary from your large file, you can easily find the highest frequency be recursively search the trie. It should be faster then a hash-Table, because the kart-trie is like an unbalance binary trie. The only difference between a kart-trie and a radix-trie, or a crip-bit-trie, is that it uses a hash-key to identify the payload. That makes is suitable for other data as well. On Oct 21, 3:35 pm, 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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: how would you find the integer pairs which sum to m in o(n) time complexity
@preetika : we can use hash table for O(n) complexity ..if array is not sorted .. i am looking for that answer... how should i make that hash table so that searching in hash table become O(1) complexity. -- 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
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: 10 most repeating words
From Wikipedia: Thus the MapReduce framework transforms a list of (key, value) pairs into a list of values. This behavior is different from the functional programming map and reduce combination, which accepts a list of arbitrary values and returns one single value that combines all the values returned by map. And what would be the difference to use a parallel algorithm such as Prim's or Dijkstra!? On Oct 22, 7:11 pm, Kishen Das kishen@gmail.com wrote: 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: how would you find the integer pairs which sum to m in o(n) time complexity
@Mohit : Then insert all the elements in hashtable and scan the hashtable in O(n) time. While scanning each elements, you have to search for (sum-element) element in the hashtable (O(1) time). What do you think? On Sun, Oct 24, 2010 at 12:51 PM, MOHIT mohit...@gmail.com wrote: @preetika : we can use hash table for O(n) complexity ..if array is not sorted .. i am looking for that answer... how should i make that hash table so that searching in hash table become O(1) complexity. -- 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.
