Re: [algogeeks] DeShaw Question....tough One
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
On 6 September 2010 14:01, bittu shashank7andr...@gmail.com wrote:
u are given an array and u have to print the longest increasing
scattered subsequence...eg..{11,9,8,2,10,7,3,4,5}.
Solve it O(n);
--
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.
--
Vignesh Radhakrishnan
--
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] String Problems
@Marcio, I get your algo now. So a substring match is also a match. I get your approach. Thank you. Any ideas for the second problem? On 20 May 2010 10:45, vignesh radhakrishnan rvignesh1...@gmail.com wrote: @Mario Your estimate of no. of strings, I guess doesn't consider strings of length less than length H or W. it would order(4H^2+4W^2) approximately. I guess I 've understood it right. correct me if I'm wrong On 20 May 2010 07:23, Mario Ynocente Castro ycma...@gmail.com wrote: I don't think 1014 needs any special algorithm, if we've got an H x W matrix, then we've got (4H+4W-2) strings in which you must look, and you can do this with a greedy strategy. 2010/5/19 vignesh radhakrishnan rvignesh1...@gmail.com I'm trying to solve some string problems somewat efficiently. Can someone tell me what would be efficient DS for solving these problems http://acm.jlu.edu.cn/joj/showproblem.php?pid=1014 http://acm.jlu.edu.cn/joj/showproblem.php?pid=1873 Thanks, Regards, Vignesh -- There are two kinds of people. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- There are two kinds of people. Those who care for others and The others -- There are two kinds of people. Those who care for others and The others -- 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] String Problems
@Mario Your estimate of no. of strings, I guess doesn't consider strings of length less than length H or W. it would order(4H^2+4W^2) approximately. I guess I 've understood it right. correct me if I'm wrong On 20 May 2010 07:23, Mario Ynocente Castro ycma...@gmail.com wrote: I don't think 1014 needs any special algorithm, if we've got an H x W matrix, then we've got (4H+4W-2) strings in which you must look, and you can do this with a greedy strategy. 2010/5/19 vignesh radhakrishnan rvignesh1...@gmail.com I'm trying to solve some string problems somewat efficiently. Can someone tell me what would be efficient DS for solving these problems http://acm.jlu.edu.cn/joj/showproblem.php?pid=1014 http://acm.jlu.edu.cn/joj/showproblem.php?pid=1873 Thanks, Regards, Vignesh -- There are two kinds of people. Those who care for others and The others -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Mario Ynocente Castro Undergraduate Student of System Engineering National University of Engineering, Peru http://sites.google.com/site/ycmario -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- There are two kinds of people. Those who care for others and The others -- 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] String Problems
I'm trying to solve some string problems somewat efficiently. Can someone tell me what would be efficient DS for solving these problems http://acm.jlu.edu.cn/joj/showproblem.php?pid=1014 http://acm.jlu.edu.cn/joj/showproblem.php?pid=1873 Thanks, Regards, Vignesh -- There are two kinds of people. Those who care for others and The others -- 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] Convert a Binary tree into spike.
do bfs. On 13 May 2010 09:18, vinayan c vinayan1...@gmail.com wrote: Something like this 1 2 3 4 5 67 1 | 2-3 | 4-5-6-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. -- There are two kinds of people. Those who care for others and The others -- 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] compute kth smallest element from union of two lists
This is for kth largest. Change it for kth smallest In fact, this problem is amenable to something very similar to binary search. Suppose my arrays are A and B. The idea is to keep track of two indices, a (for A) and b (for B), such that a + b = k - 1 (it's very important to maintain this invariant). It's easy to check whether A[a] or B[b] is the answer: A[a] is the answer if and only if B[b-1] = A[a] = B[b], and B[b] is the answer if and only if A[a-1] = B[b] = A[a], where we use the convention that A[-1] = B[-1] = negative infinity. (This can be determined in constant time.) Moreover, if neither of these is the case, you can divide the problem in half: if A[a] B[b-1], you restrict your attention to the portion of A above index a and the portion of B below index b, and otherwise (it must be the case that B[b] A[a-1]), you restrict your attention to the portion of A below index a and the portion of B above index b. (If you start with a and b in the middle of the arrays and always make the new indices be in the middle of the subarrays you're considering at that point, this step will always divide the problem in half.) Thanks to Lux Perpetua http://forums.devshed.com/member.php?u=74699 source: http://forums.devshed.com/software-design-43/finding-kth-largest-element-in-a-union-of-two-arrays-137322.html On 13 May 2010 19:34, divya sweetdivya@gmail.com wrote: You are given two sorted lists of size m and n. Give an O(log m+log n) time algorithm for computing the kth smallest element in the union of the two lists -- 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. -- There are two kinds of people. Those who care for others and The others -- 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] 400!
@siddharth and prasoon either design a very long integer library yourself, or use gmp library in cpp or BigInteger Class in java. Regards, vignesh On 3 May 2010 09:46, siddharth srivastava akssps...@gmail.com wrote: But is there any way to accomplish this without an array ? Even for 100!. On 2 May 2010 06:15, Prasoon Mishra prasoonbluel...@gmail.com wrote: I think challenge here is not the Execution time, but the storage. 300 ! or 400! should generally go beyond the storage capabilities of long long ints in cpp. @ Rohit Saraf: Hence, I don't know if even tail recursion will ultimately be able to store the output. I think Rajesh Patidar's answer fits the bill well, in terms of storage. On Sun, May 2, 2010 at 2:23 PM, vignesh radhakrishnan rvignesh1...@gmail.com wrote: I agree with abhijith. But given some very large x for which i would have to find factorial. I would either (i) use gmp in cpp or BigInteger or java if its not a lab exercise or an interview (ii) use simple brute multiplication algorithm. The second approach requires (a) The no. of digits in n! for making storage available (b) The calculation itself which I would brute force References: http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it http://delphiforfun.org/programs/big_factorials.htm On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: google it... u will gt it i am on mobile... cannot explain now.. On 5/2/10, divya jain sweetdivya@gmail.com wrote: wat is tail recursion plz explan in detail On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @divya use tail recursion and rest should be fine.. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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.comalgogeeks%252bunsubscr...@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. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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. -- There are two kinds of people. Those who care for others and The others -- 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. -- Siddharth Srivastava Human Knowledge is for all -- 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. -- There are two kinds of people. Those who care for others
Re: [algogeeks] a google question
@divya You're rite. Post a solution if you have one.
--
Regards,
Vignesh
On 2 May 2010 13:14, divya jain sweetdivya@gmail.com wrote:
@Mohit
according to ur algo if a[1], b[0] has sum greater than a[0],b[1]
then i is incremented i is now 2 so for next iteration u ll compare a[2]
b[0] and a[1] b1]. but what about a[0] b[1] this pair s lost forever. think
for ths case also.
On 2 May 2010 11:22, mohit ranjan shoonya.mo...@gmail.com wrote:
@Algoose Chase
point taken
Thanks
Mohit Ranjan
Samsung India Software Operations.
On Sat, May 1, 2010 at 8:43 PM, Algoose Chase harishp...@gmail.comwrote:
@mohit
The idea of DP is fine.
When you find the Max i dont think you need to include A[i+1]+B[j+1]
because it can never be greater than both A[i+1]+B[j] and A[i]+B[j+1] since
both the lists are sorted in decreasing order.
On Fri, Apr 30, 2010 at 8:47 PM, mohit ranjan
shoonya.mo...@gmail.comwrote:
oops
Sorry didn't read properly
last algo was for array sorted in ascending order
for this case, just reverse the process
A[n] and B[n] are two array
loop=n, i=0, j=0;
while(loop0) // for n largest pairs
{
print A[i]+B[j]; // sum of first index from both array will
be max
foo = MAX ( A[i+1]+B[j], A[i+1]+B[j+1], A[i]+B[j+1] ) // using DP,
moving forward
if foo==A[i+1]+B[j]; i++ // only increment A
if foo==A[i+1]+B[j+1]; i++; j++ // increment both A and B
if foo==A[i]+B[j+1]; j++ // increment only B
}
Mohit Ranjan
Samsung India Software Operations.
On Fri, Apr 30, 2010 at 8:40 PM, mohit ranjan
shoonya.mo...@gmail.comwrote:
Hi Divya,
A[n] and B[n] are two array
loop=n, i=n-1, j=n-1;
while(loop0) // for n largest pairs
{
print A[i]+B[j]; // sum of last index from both array will
be max
foo = MAX ( A[i-1]+B[j], A[i-1]+B[j-1], A[i]+B[j-1] ) // using DP
moving backward
if foo=A[i-1]+B[j]; i-- // only reduce A
if foo=A[i-1]+B[j-1]; i--; j-- // reduce both A and B
if foo=A[i]+B[j-1]; j-- // reduce only B
}
Time: O(n)
Mohit Ranjan
On Fri, Apr 30, 2010 at 5:35 PM, divya sweetdivya@gmail.comwrote:
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.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 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.
--
There are two kinds of people. Those who care for others and The others
--
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] 400!
I agree with abhijith. But given some very large x for which i would have to find factorial. I would either (i) use gmp in cpp or BigInteger or java if its not a lab exercise or an interview (ii) use simple brute multiplication algorithm. The second approach requires (a) The no. of digits in n! for making storage available (b) The calculation itself which I would brute force References: http://inder-gnu.blogspot.com/2009/08/find-number-of-digits-in-factorial-of.html http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it http://delphiforfun.org/programs/big_factorials.htm On 2 May 2010 13:59, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: google it... u will gt it i am on mobile... cannot explain now.. On 5/2/10, divya jain sweetdivya@gmail.com wrote: wat is tail recursion plz explan in detail On 2 May 2010 08:15, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @divya use tail recursion and rest should be fine.. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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.comalgogeeks%252bunsubscr...@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. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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. -- There are two kinds of people. Those who care for others and The others -- 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] Divide and Conquer problem
You 've got n teams and nC2 ways of conducting the matches with specified constraints that's n/2(n-1). So, each day you need to conduct n/2 matches such that, no team repeats within a day, no match that was previously held repeats. Since the problem has an unique solution, you can either brute force it with a program or design an back track solution. regards, vignesh On 7 April 2010 12:20, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Can any one help me with this problem Its a divide and conquer problem where, there are n teams and each team plays each opponent only once. And each team plays exactly once every day. If n is the power of 2, I need to construct a timetable allowing the tournament to finish in n-1 days... Any help would be appreciated.. thanks -- 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] Cartesian Product in set theory
The unordered pair will be a subset of cartesian product. What is the significance of it? On 8 February 2010 21:18, pinco1984 paris...@gmail.com wrote: Hi all, I have came across a problem and I am not aware if there is such a thing in set theory and if so what is it called. Mainly I have several sets that I am interested in their cartesian product. But this cartesian product should not be a set of ordered pairs but a set of sets. Basically unordered pairs. I wonder if this concept is well defined and what is it called. Thanks. P. -- 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.
