Re: [algogeeks] Re: a google question
I guess your solution would also be proved incorrect with the following,
Numbers in bold are the two arrays.
125 122 120 110 104 103 102 101
100 999897
130255 252 250 240 234 233 232 231 230
229 228 227
128 253 250 248 238 232 231 230 229 228
227 226 225
126 251 248 246 236 230 229 228 227 226
225 224 223
125 250 247 245 235 229 228 227 226 225
224 223 222
105 230 227 225 215 209 208 207 206 205
204 203 202
104229 226 224 214 208 207 206 205 204
203 202 201
103228 225 223 213 207 206 205 204 203
202 201 200
102227 224 222 212 206 205 204 203 202
201 200 199
101226 223 221 211 205 204 203 202 201
200 199 198
100 225 222 220 210 204 203 202 201 200
199 198 197
99 224 221 219 209 203 202 201 200 199
198 197 196
98 224 221 219 209 203 202 201 200 199
198 197 196
manish...
From: Varun Nagpal varun.nagp...@gmail.com
To: Algorithm Geeks algogeeks@googlegroups.com
Sent: Mon, 3 May, 2010 12:26:24 PM
Subject: Re: [algogeeks] Re: a google question
Guys no one commented on my solution? Any takes on it?
Anyways, below is my solution (in pseudo code)
Pre-condition: A and B are sequences of equal length and sorted in
descending order
Input: Sequences A[1..N] and B[1..N] of equal lengths(N)
Ouput: Sequence C[1..N] containing sorted sum of ordered pairs from
cartesian products of A, B or B,A
Sort(A,B)
{
k = 1
N = length(A) = length(B)
C[1..2*N] = []// Empty array
cart_prod_order = 0 // 0 - AxB, 1 - BxA. 0 is default
// Complexity : O(N)
while(k != N+1)
{
if (A[k] B [k])
{
cart_prod_order = 1
break
}
else
{
k = k + 1
}
}
// Choose the correct order of Cartesian product sum
// Complexity: Theta(2N) = O(N)
if (cart_prod_order == 1)
{
// take cartesian product of B and A, storing the sum of ordered
pair (b,a) in each element of C
C[1..2N] = B[1..2] x A[1..N]
}
else
{
// take cartesian product of A and B, storing the sum of ordered
pair (a,b) in each element of C
C[1..2N] = A[1..2] x B[1..N]
}
// Merge
// C[1..N] and C[N+1..2N] are already sorted in descending order
// Complexity: Theta(N)
C[1..2N] = Merge(C[1..N],C[N+1..2N])
return C[1..N]
}
Merge(C,D)
{
i=1,j=1,k=1
E = []
while(i=length(C) OR j=length(D))
{
if(i=length(C) AND (jlength(D) OR C[i]D[j]))
{
E[k] = C[i]
i = i + 1
}
else
{
E[k] = D[j]
j = j + 1
}
k = k + 1
}
return E;
}
On Fri, Apr 30, 2010 at 7:50 PM, banu varun.nagp...@gmail.com wrote:
Nice question:
1. |A| = |B| i.e I assume their cardinality is equal
2. A(n) = { a1, a2 a3, ...aN} such that a1=a2=a3...=aN
3. B(n) = { b1, b2 b3, ...bN} such that b1=b2=b3...=bN
4. S(n^2) = A x B = {(a1,b1), (a1,b2)(a1,bN),
(a2,b1), (a2,b2)(a2,bN),
(aN,b1), (aN,b2)(aN,bN)}
assuming we have added in a way such that we find a pair ai bi,
for some i in 1..N such that a(i-1) = b(i-1)
A first observation is that in the worst case, the first 2N numbers in
S will contain the final result of N numbers.
i.e in (a1,b1), (a1,b2)(a1,bN), (a2,b1), (a2,b2)(a2,bN)
In the best case first N numbers in S will contain the final N numbers
(already sorted in decreasing order)
i.e in (a1,b1), (a1,b2)(a1,bN)
Now, if we consider again the worst case scenario, then we can first
divide 2N numbers in two groups of size N each and each of this group
is already sorted in decreasing order.
i.e (a1,b1), (a1,b2)(a1,bN) and (a2,b1), (a2,b2)(a2,bN)
Now we can simply apply Merge Algorithm on these 2 already sorted
arrays of size N each in O(N) time, which solves the problem
I can be wrong only if the the results lie outside first 2N
numbers(which I hope is not the case).
On Apr 30, 2:05 pm, 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
Re: [algogeeks] a google question
How are we making sure that top n-elements would lie in this 'L' shaped array? Also, why don't we take an extreme case, such that the origin is bottom-left element of the grid, then we have only 2n-1 elements to chose n biggest elements from. So, can we prove that taking Ist quardrant as (n-2)x(n-3) would leave n-biggest out? What is the criterion to chose the Ist quardrant? manish... From: topojoy biswas topojoy.bis...@gmail.com To: algogeeks@googlegroups.com Sent: Thu, 22 July, 2010 10:10:58 AM Subject: Re: [algogeeks] a google question im sry the L should look like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 I missed a row in the last mail. On Thu, Jul 22, 2010 at 10:03 AM, topojoy biswas topojoy.bis...@gmail.com wrote: consider these arrays: 10 9 8 5 3 2 1 and 13 12 11 10 9 8 7 form a grid like this: 109 8 5 321 7 17 1615 1210 98 8 18 1716 1311 10 9 9 19 1817 1412 12 10 10 20 1918 1513 12 11 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 basically have an array descending and have one array ascending. If you add them in a grid, check that for any sum, all sums to its right are less than it( in the same row), al sums above it( in the same column) are less than it, all sums below it( in the same row) are greater than it. 109 8 5 321 7 17 1615 1210 98 8 18 1716 1311 10 9 9 19 1817 1412 12 10 10 20 1918 1513 12 11 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 So all sums which form the first quadrant origining at 19 are less than 19. And the 3rd quadrant formed by origining 19 including 19 are strickedly grater than or equal to 19. This means in the added array will look like this: __ ||___|__| ---xmy- x = no of elements in the underlined first quadrant y= no of elements in the 3rd quadrant excluding 19. m= the number of elements in the 2nd and the 4th quadrant including 19. So 19 would lie some whr in the 2n slot of this divided aray picture. So if we make x big enough so that m+y is small enough=O(n), we will reduce our load. so choose x=(n-2)(n-3) which means something like this: --(n-2)--- 109 8 5 321 7 17 1615 1210 98 --- 8 18 1716 1311 10 9 9 19 1817 1412 12 10 (n-3) 10 20 1918 1513 12 11 - 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Then we will be left with an array of size m+y=5n-6 which is n for all n 2 like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 20 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Till this point it takes constant time. Now the first column of the L formed is sorted. So is the 2nd column. So is the horizonal part of L which is comprized of two sorted arays (20-13) and (21-14). All of the elements add to 5n-6. We can merge sort them in O(n) time. Take the biggest n elements. On Mon, Jul 19, 2010 at 12:18 PM, ankur aggarwal ankur.mast@gmail.com wrote: this ques was asked by google.. i* could find any gud soln than order n*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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- 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] a google question
It doesn't work
A =
92 87 81 72 70 61 53 22 18 17
B =
79 78 74 68 64 62 57 34 29 24
C (GOLD) =
171 170 166 166 165 161 160 160 159 156
D (TEST) =
171 170 166 166 165 159 155 155 146 145
Result: FAILED!
manish...
From: Jitendra Kushwaha jitendra.th...@gmail.com
To: algogeeks@googlegroups.com
Sent: Sun, 2 May, 2010 9:13:14 PM
Subject: Re: [algogeeks] a google question
Here is a solution of O(n) , taking 4 pointers 2 for each array
#include cstdio
#includeiostream
using namespace std;
#define N 10
int main(void)
{
int arr1[N] = {8,7,4,3,2,1,1,1,1,1};
int arr2[N] = {34,23,21,19,15,13,11,8,4,2};
int *p11,*p12,*p21,*p22;
p11 = p12 = arr1;
p21 = p22 = arr2;
int f1;
f1 = 0;
for(int i=0;iN;i++) {
int ans=0;
int a,b,c,d;
a = *p11 + *p21;
b = *p11 + *p22;
c = *p21 + *p12;
d = *(p11+1) + *(p21+1);
//printf(a=%d b=%d c=%d d=%d\n,a,b,c,d); //debug
if(f1==0)ans = a ,p12++ , p22++ , f1=1;
else if(b = c b = d )ans = b , p22++ ;
else if(c = b c = d )ans = c , p12++ ;
elseans = d , p11++ , p21++ ,printf(4 );
printf(%d\n,ans);
}
}
Regards
Jitendra Kushwaha
Undergradute Student
Computer Science Eng.
MNNIT, Allahabad
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: random number...
How are you picking ni from [a...b] range (length 7) ? From: avalon avalo...@gmail.com To: Algorithm Geeks algogeeks@googlegroups.com Sent: Saturday, 19 September, 2009 2:16:47 PM Subject: [algogeeks] Re: random number... Forgive me first if i am wrong since i didn't read all the posting ... Here is a way to sol the problem. n1 = random_1_5() + 0; n2 = random_1_5() + 5; .. n7= random_1_5() + (7-1)*5; now n1 ... n7 is in range [1 ... 35] Image we divde the range [1.. 35] into 5 parts, such as [1...7] , [8...14] ... then we generat n8 = random_1_5() we use n8 to pick a part we divided above. so we get a range [a...b] , then we can get a number ni inside the range, return ni; ankur aggarwal ankur.mast@gmail.com wrote: Given a random number generator that generates numbers in the range 1 to 5, how can u create a random number generator to generate numbers in the range 1 to 7. (remember that the generated random numbers should follow a uniform distribution in the corresponding range) Try the new Yahoo! India Homepage. Click here. http://in.yahoo.com/trynew --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] selection from infinite tape
There is an infinite tape running, churning out numbers. You are able to see these numbers one by one, but not allowed to store all of them, but you should be ready with k numbers whenever prompted, such that all have been selected with equal probability. Say, when you were prompted, n numbers have already passed, each of your selected k numbers should have 1/n as the selection probablity. Of course, you can store k numbers from that tape as the tape is progressing, so that you can present them when prompted. Now, send attachments up to 25MB with Yahoo! India Mail. Learn how. http://in.overview.mail.yahoo.com/photos --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: max product of any three nos in an array of signed integers
1. Sort the array (say arr) (O(nlgn)
2. Find the position of 0 in the array. The left of the array would be all -ve
and right of the array is all positive. Say zi is the position of zero, so
indices [0, zi) are all -ve and (zi, n-1] are all +ve. (O(lgn). If 0 is not
there in the array, we can still find its position, say it is b/w ith and
(i+1)th index. Then the -ve array would be with indices [0, i], and +ve array
would be (i, n-1].
3a. if(zi == n-1) // arr contains -ve elements only
return arr[0]*arr[1]*arr[2];
3b. if(zi == 0) // arr contains +ve elements only
return arr[n-1]*arr[n-2]*arr[n-3];
3c. return max{arr[n-1]*arr[n-2]*arr[n-3], arr[n-1]*arr[zi-1]*arr[zi-2]};
Only other cases remaining are boundry conditions, for e.g. if -ve array size
is 1, or when +ve array size is 3.
So seems doable in O(nlgn + lgn).
From: SP Praveen praveen.sel...@gmail.com
To: Algorithm Geeks algogeeks@googlegroups.com
Sent: Sunday, 13 September, 2009 7:04:37 PM
Subject: [algogeeks] max product of any three nos in an array of signed integers
Given an array of integers (signed integers), find three numbers in
that array which form the maximum product.
Now, send attachments up to 25MB with Yahoo! India Mail. Learn how.
http://in.overview.mail.yahoo.com/photos
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: max product of any three nos in an array of signed integers
This one is better than what I suggested before. Doable in O(n)! On Sep 13, 10:10 pm, Dave dave_and_da...@juno.com wrote: The following assumest that n = 5. Find the 3 largest positive numbers and the two largest-in-magnitude negative numbers (i.e., the two smallest signed numbers). If there are not two negative numbers, the 3 largest positive numbers are the answer. Otherwise, if there are only one or two positive numbers, the largest positive number and the two largest-in-magnitude negative numbers are the answer. Otherwise, compare the product of the three largest positive numbers with the product of the largest positive number and the two largest-in- magnitude negative numbers. The answer is whichever set produces the largest product. If the product of the answer set is zero, the answer will not be uniquely determined. This can be done in O(n) time and O(1) extra space. Dave On Sep 13, 8:34 am, SP Praveen praveen.sel...@gmail.com wrote: Given an array of integers (signed integers), find three numbers in that array which form the maximum product. Try the new Yahoo! India Homepage. Click here. http://in.yahoo.com/trynew --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: random number...
Dave,
You are correct about the first approach. It is biased towards '1' and of
course 000 goes waste.
With the second approach, I couldn't find a uniform distribution, because there
is no power of 5 which is a multiple of 7, as they are relatively prime. For
the errornous approach where 1 transition goes waste, code should be very
simple. Here is a prototype,
int rand_1_7() {
int f = 15624/7;
// since transitions are already random, lets divide 15624 uniformly for
each of 1,2,..,7
// lets imagine a number with base 5, so 15625 is 100, and 15624 will
be 44.
// suppose each call to rand_1_5() gives one bit for the number
int b1 = rand_1_5()-1; // 1 is substracted to bring the numbers to the range
[0,4]
int b2 = rand_1_5()-1;
int b3 = rand_1_5()-1;
int b4 = rand_1_5()-1;
int b5 = rand_1_5()-1;
int b6 = rand_1_5()-1;
int num = (5^5)*b6 + (5^4)*b5 + (5^3)*b4 + (5*2)*b3 + (5^1)*b2 + (5^0)*b1;
if(num = f) return 1;
if(num = 2*f) return 2;
if(num = 3*f) return 3;
if(num = 4*f) return 4;
if(num = 5*f) return 5;
if(num = 6*f) return 6;
return 7;
}
From: Dave dave_and_da...@juno.com
To: Algorithm Geeks algogeeks@googlegroups.com
Sent: Wednesday, 9 September, 2009 2:42:26 AM
Subject: [algogeeks] Re: random number...
Manish, your first approach doesn't work. You will notice that b1, b2,
and b3 each are 0 2/5 of the time and 1 3/5 of the time, so the return
value is not uniformly distributed.
For approach 2, what do you have to do if you want an exactly uniform
distribution as a result? Or what would the code look like for one of
your non-exact methods?
Dave
On Sep 8, 1:32 pm, manish bhatia mb_mani...@yahoo.com wrote:
I can think of 2 appraches.
[1] Similar to something already suggested. Just adding my 2 cents.
1 to 7 digits can be represented by 3 bits. So going by that,
int rand_1_7() {
b1 = rand_1_5()*(7/5) (7/2) ? 1 : 0;
b2 = rand_1_5()*(7/5) (7/2) ? 1 : 0;
b3 = rand_1_5()*(7/5) (7/2) 1 : 0;
return (b1*4 + b2*2 + b3*1);
}
[2] What we are trying to do is map numbers 1 to 5 to numbers 1 to 7. Of
course mapping 5 items to 7 items is not straight forward. So lets not map
items, but map transitions. Suppose an imaginary initial state x. Now when we
call rand_1_5(), we have one of the following transition,
1) x - 1
2) x - 2
3) x - 3
4) x - 4
5) x - 5
Now, lets call rand_1_5() again, and remember the last transition, viz.
1) x - 1 - 1
2) x - 1 - 2
24) x - 5 - 4
25) x - 5 - 5
So we have 25 transitions. Divide it by 7, we get 4 as remainder and 3 as
quotient i.e. if we each number 1 to 7, three of these 25 transitions each,
we get 4 unused transitions. Lets take it to next level. We get 25*5 = 125
transitions. Divide by 7, we get 6 unused transitions. Still another level,
get us 125*5 = 625 transition, divide by 7, we get 2 as remainder. So nearest
we get is, 625*5*5 = 15624. Dividing by 7, we get 1 as remainder. So in 15625
transitions, (by calling rand_1_5() 6-times), we can assign 2232
unique-transitions to each on of 1,2,..,7. With just 1 un-assigned
transition, we get 1/15625 part-error, or 0.0064% error.
Comments?
On Sep 7, 10:56 am, ankur aggarwal ankur.mast@gmail.com wrote:
Given a random number generator that generates numbers in the range 1 to
5, how can u create a random number generator to generate numbers in the
range 1 to 7. (remember that the generated random numbers should follow a
uniform distribution in the corresponding range)
Love Cricket? Check out live scores, photos, video highlights and more.
Click herehttp://cricket.yahoo.com
Looking for local information? Find it on Yahoo! Local
http://in.local.yahoo.com/
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: n balls having k colors
Assign 0 to K numbers to all K colors, such that color - color_tag (a number
b/w [0,K-1]).
code[k] = {0,2,..,k-1}
foreach (permutation from all possible-permuations of code[])
sort balls[] on the basis of code[color_tag]
print balls[]
From: ankur aggarwal ankur.mast@gmail.com
To: lets-talk-g...@googlegroups.com; algogeeks@googlegroups.com
Sent: Sunday, 6 September, 2009 1:36:01 PM
Subject: [algogeeks] n balls having k colors
You have N balls having one of K colors. Arrange them into groups of same
colors. e.g.
RRGRG
can be arranged as
RRRGG (Answer)
GGRRR
See the Web#39;s breaking stories, chosen by people like you. Check out
Yahoo! Buzz. http://in.buzz.yahoo.com/
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: linked list questions
Are we able to store the incoming characters? On Tue, Sep 8, 2009 at 11:51 AM, Bharath bharath1...@gmail.com wrote: Slightly modifying first question. Check whether a string is palindrome in single pass. Meaning an online algorithm is required, i.e. it must be able to read one character at a time from a stream and tells whether string read so far is palindrome or not. See the Web#39;s breaking stories, chosen by people like you. Check out Yahoo! Buzz. http://in.buzz.yahoo.com/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: n balls having k colors
From: ankur aggarwal ankur.mast@gmail.com
To: algogeeks@googlegroups.com
Sent: Tuesday, 8 September, 2009 9:02:45 PM
Subject: [algogeeks] Re: n balls having k colors
int num_balls[K] = {0}; // one entry per color.
Use num_balls[] to count balls for each color. Now we just need to permute
num_balls[].
sort balls[] on the basis of code[color_tag]
wat r u doing here ??
Well for what its worth, here I am sorting balls[] array such that instead of
comparing balls[i] balls[j], I am comparing, code[color(balls[i])]
code[color(balls[j])].
On Tue, Sep 8, 2009 at 8:35 PM, manish bhatia mb_mani...@yahoo.com wrote:
Assign 0 to K numbers to all K colors, such that color - color_tag (a number
b/w [0,K-1]).
code[k] = {0,2,..,k-1}
foreach (permutation from all possible-permuations of code[])
sort balls[] on the basis of code[color_tag]
print balls[]
From: ankur aggarwal ankur.mast@gmail.com
To: lets-talk-g...@googlegroups.com; algogeeks@googlegroups.com
Sent: Sunday, 6 September, 2009 1:36:01 PM
Subject: [algogeeks] n balls having k colors
You have N balls having one of K colors. Arrange them into groups of same
colors. e.g.
RRGRG
can be arranged as
RRRGG (Answer)
GGRRR
See the Web's breaking stories, chosen by people like you. Check out Yahoo!
Buzz.
@manish
wat is the complexity ??
think about it...
Yeah complexity is way off! Perhaps we can do the following (provided we can
use extra space).
See the Web#39;s breaking stories, chosen by people like you. Check out
Yahoo! Buzz. http://in.buzz.yahoo.com/
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Find longest palindrom in a give n string in O(N)
Could you please elaborate? From: ankur aggarwal ankur.mast@gmail.com To: algogeeks@googlegroups.com Sent: Tuesday, 1 September, 2009 6:01:51 PM Subject: [algogeeks] Re: Find longest palindrom in a give n string in O(N) On Tue, Sep 1, 2009 at 2:24 PM, Nayn nayanish.hi...@gmail.com wrote: Working with stack doesn't work. Push down Automata is usefull in checking if a given string in palindrom or not... But useless for finding longest palindrom. correct dufus Love Cricket? Check out live scores, photos, video highlights and more. Click here http://cricket.yahoo.com --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: path from n1 to n2
A simple DFS should give you this (populating the path as we do the traversal). Now only question is when we get a forward-edge, i.e. a convergence-point, we have two options, (Assuming that while coming back after hitting n2, we keep marking vertices which have n2 in the fanout, similarly mark nodes which do not have n2 in the fanout). Suppose we hit vertex v which is already visited and it has n2 in the fanout, (if n2 is not in the fanout, nothing to do, go back) 1. Allow traversal via this node and let it hit n2 again. This is memory-efficient but would take more run-time. 2. When you are coming back after hitting n2, at any vertex where there are more than one in-arcs, i.e. a potential convergence point, keep the path v-onwards, which will lead to n2. Now this will get complex in case of re-convergence, because then there will be more than one paths from v to n2. From: ankur aggarwal ankur.mast@gmail.com To: i...@mca_2007 iit_rmca_2...@googlegroups.com; lets-talk-g...@googlegroups.com; algogeeks@googlegroups.com Sent: Wednesday, 26 August, 2009 2:03:01 PM Subject: [algogeeks] path from n1 to n2 given a directed graph and node n1 and n2 find all possible path between them i think graph is acyclic .. otherwise there are infinte path we can write eg for node a and d are there we have a cycle node b to c and c to b a- b-c-b-d a- b-c-b-c-b-d etc Yahoo! recommends that you upgrade to the new and safer Internet Explorer 8. http://downloads.yahoo.com/in/internetexplorer/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: path from n1 to n2
How should a toposort help? From: ankur aggarwal ankur.mast@gmail.com To: algogeeks@googlegroups.com Sent: Thursday, 27 August, 2009 9:15:47 AM Subject: [algogeeks] Re: path from n1 to n2 @ _dufus i also think dfs can solve this problem widout topological sort Fitness on your mind? Check out nearby gyms on Yahoo! India Local http://in.local.yahoo.com/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Merging companies
Suppose nCp represents n!(n-p)!/p! The product of the following should be the answer, nC2 x (n-1)C2 x (n-2) x ... x 2C2 The above assumes that merger of company K1 with K2, gives rise to a new company K12, and merger of K12 with K3, and K13 with K2 is different. How does it sound? From: ankur aggarwal ankur.mast@gmail.com To: algogeeks@googlegroups.com; i...@mca_2007 iit_rmca_2...@googlegroups.com; lets-talk-g...@googlegroups.com Sent: Tuesday, 25 August, 2009 12:28:48 AM, Subject: [algogeeks] Merging companies Merging companies Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge? Love Cricket? Check out live scores, photos, video highlights and more. Click here http://cricket.yahoo.com --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Check divisibility by 3
Keep adding the digits till you are reduced to single digit. Then check if it is 3, 6 or 9 From: richa gupta richa.cs...@gmail.com To: programming-puzzles programming-puzz...@googlegroups.com; algogeeks algogeeks@googlegroups.com Sent: Friday, 14 August, 2009 1:15:13 PM Subject: [algogeeks] Check divisibility by 3 can we check the divisibility of a given number by 3 withoutusing operators like '/' or '%'. I want the efficient solution to this problem .. can someone help ?? -- Richa Gupta (IT-BHU,India) See the Web#39;s breaking stories, chosen by people like you. Check out Yahoo! Buzz. http://in.buzz.yahoo.com/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Finding repeated element in most efficient way
Well instead of using extra memory, we can in-place sort the arraay in O(nlog(n)) and then do an iteration (O(n)) to find out the repeated number. But the catch is that number is repeated 2^i times. That is the hint we should use From: ankur aggarwal ankur.mast@gmail.com To: algogeeks@googlegroups.com Sent: Sunday, 9 August, 2009 5:47:32 PM Subject: [algogeeks] Re: Finding repeated element in most efficient way @richa.. ques is in complete i think . there shud be some conditions given .. otherwise hash them but lots of space will b wasted.. or sort them try to put the conditions.. Yahoo! recommends that you upgrade to the new and safer Internet Explorer 8. http://downloads.yahoo.com/in/internetexplorer/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Spell Checker
He meant alternate-spellings! Just like you get from MS-Word et. al. From: Vikram Sridar vikramsridar...@gmail.com To: algogeeks@googlegroups.com Sent: Friday, 31 July, 2009 7:03:54 PM Subject: [algogeeks] Re: Spell Checker Alternatives?? what way?? In terms of implementation or providing some other functionalities?? See the Web#39;s breaking stories, chosen by people like you. Check out Yahoo! Buzz. http://in.buzz.yahoo.com/ --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
