[algogeeks] Re: Find the number of paths between two points on a grid
Hi, That makes sense. I always thought as nodes. A 2x2 grid is square box, right? m = 2 and n = 2, C(4,2) = 6. Is it right? Lei --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
Hey Buddy, NxM grid means that n is the no. of horizontal line and M is the no. of vertical lines. for a single line n=1 and m=0 so formula is C(1,0)...this gives the output 1. On 4/6/06, [EMAIL PROTECTED] < [EMAIL PROTECTED]> wrote: I am wondering how you get the formula.If you have n = 1 and m = 2 which is a single line with 2 points, there should be 1 path between the two node. But your formula gives 3.LeiBy the way...the First thing is ur KISS :-) Prashant Bhargava-- www.excogitation.tk or www.hemantdesign.com/prashant --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Problem
Is the solution always x = N-4, y = N-3, z = N-2 ? Suppose we are looking for x and y to minimize the sum. Sum = a[i]*x + a[j]*y, where 0 <= i <= x < j <= y <= N. It is always bigger than a[i]*x + a[j]*x, because x < y and all numbers are positive. We have to have a y so when y is the last one, the sum is the minimum. Similarly, z should be the last one too. Any counterexample? Lei --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
I am wondering how you get the formula. If you have n = 1 and m = 2 which is a single line with 2 points, there should be 1 path between the two node. But your formula gives 3. Lei --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
i don't understand, i am pretty new at programming. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Subset with largest sum
Yes, am sorry, its infact the continous sub-sequence which I missed in the question. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Linking sibling in a binary tree
If I understand it correctly, how about just do a BFS search from root of this tree. We can find the sibling nodes easily in its FIFO and link them, right? --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Length of internal path in a binary tree
For a binary tree with N nodes, I think it will have n-1 edges. So the totoal lenght is n-1. Am I right? --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Subset with largest sum
I think it it max sub-sequence problem which is discussed on this link : http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=3052 On 4/5/06, Vijendra Singh <[EMAIL PROTECTED]> wrote: I dont get it, if its just the subset, then just get the sum of all positive nos. may be you wanted continous nos.another variation of the question can be, find the subset where (sum of subset)/(max element of the set) is maximum. Lets discuss this as well :)Thanks,Vijendra On 4/5/06, shishir <[EMAIL PROTECTED] > wrote: Hi,This is a standard MS interview question.Give an O(n) algorithm to find the subset of an array A[n] with largest sum.Anticipating a healthy and useful discussion on this.Thanks,ShishirIndian Institute of Technology, Kharagpur. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Subset with largest sum
I dont get it, if its just the subset, then just get the sum of all positive nos. may be you wanted continous nos.another variation of the question can be, find the subset where (sum of subset)/(max element of the set) is maximum. Lets discuss this as well :)Thanks,VijendraOn 4/5/06, shishir <[EMAIL PROTECTED] > wrote:Hi,This is a standard MS interview question.Give an O(n) algorithm to find the subset of an array A[n] with largest sum.Anticipating a healthy and useful discussion on this.Thanks,Shishir --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Subset with largest sum
Hi, This is a standard MS interview question. Give an O(n) algorithm to find the subset of an array A[n] with largest sum. Anticipating a healthy and useful discussion on this. Thanks, Shishir --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the number of paths between two points on a grid
For a nxm grid of nodes the no of possible paths between the two nodes each of them at a corner of the grid and under the constraint that a node should not be repeated is given by (n+m) C n = (n+m)!/(m!n!) = (n+m) C m. Is this what you are looking for.? --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: I guess, It is a tough one!!! Lets see who solves this
Hi rainix,
I feel that this solution is not correct.
if a[i] + b[j] < a[i-1]+b[n]
we decrease i;
this means that the previous a[i] is never considered again with any
other elements of B. It should be considered again because the
a[i-1]+b[n] is being decreased continuously.
Please correct me if i am wrong.
> i think this ALGO can resovle the problem
>
> 1) do comparison from a[n]+b[n] because it is the largest number in
> the new set;
> 2) can think those numbers, including a[i]+b[n], a[i]+b[n-1],
> a[i]+b[n-2], ... untill a[i]+b[j] are a part of n largest numbers in the new set;
> 3) if a[i]+b[j] 0, then let i = i-1, and
> recursively do the step 2); else
> 4) if a[i]+b[j] numbers, then find the remained largest numbers from a[1]+b[n] to
> a[1]+b[1].
>
> psuedo-code:
> find (i)
> {
> if (i = 0)
> {
> for (j=n; j>count; j--)
> print (a[1]+b[j]);
> return;
> }
>
> for (j=n, j<=0; j--)
> {
> if (a[i]+b[j] break;
> print (a[i]+b[j]);
> count ++;
> if (count == n)
> return;
> }
>
> find(i--);
>
> return;
> }
>
> time cost: 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 algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: N -ROOM LIGHTS PROBLEM
hooo --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: I guess, It is a tough one!!! Lets see who solves this
Hi Arunachalam!
Good work! Is there some way you can stop duplicates in the final
answer? i.e; ai+bj can be considered more than once as answer.
Sorry, i am poor at mathematics so can't figure it out how to get its
running time.
But still there is some way that we can get O(n) even in worst case
think...:)
Arunachalam wrote:
> Here is the improvement to my previous algorithm.
>
> Observation 1.
> ax+by can appear in the solution only if ax+bj has appeared in the
> solution where j > y.
>
> Observation 2.
> ax+bn can be included only if a(x+1)+bn is included in the answer.
>
> 1. Extract an+bn as the maximum
> 2. Form a heap with a(n-1)+b(n) and a(n)+b(n-1).
> 3. Extract the maximum from the heap ( assume max extracted is ai+bj )
> 4. Add ai+b(j-1) to the heap
> 5. Add a(i-1)+bn also to the heap if the extracted max is ai+bn.
>
> So the worst case complexity for this log(n)+log(n-1)+..1.
>
> The best case is O(n) where the heap will have only 2 elements.
>
> PS: can someone prove using amortized analysis this solution has the
> complexity of O(n).
>
>
> On 4/3/06, Mayur <[EMAIL PROTECTED]> wrote:
> >
> > It doesn't matter. It's not correct. :((
> >
> > Here's what the algo does: -
> > It was basically an attempted patch to the problem you indicated: -
> >
> > curMin is the largest number which was not considered for printing at some
> > stage - but might be useful at some
> > other stage...
> >
> > Select an + bn
> > Next select either a(n-1) + bn or an + b(n-1), setting the other one to
> > curMin (or current-minimum).
> > i.e. Follow the sequence (let arbitrarily a(n-1)+b(n) be larger)
> >
> > an + bn
> > a(n-1) + bn
> > a(n-2) + bn
> > ...
> > a(n-k) + bn. <-- at some k, the value of a(n-k) + bn would be smaller
> > than curMin. In this case,
> > print whatever's there in current-min
> > Let the pointer 'j' "surge" ahead
> > Set curMin to be a(n-k) + bn (this number was not
> > printed), and set the surged-ahead flag to B.
> > Reset the pointer "i" to the last-position again ...
> >
> > Something like this: --
> > an + bn, a(n-1)+b(n), a(n-2)+b(n) ... a(n-k)+b(n) a(n) + b(n-1)
> > --> a(n-1)+b(n-1), a(n-2)+b(n-1), .. a(n-k') + b(n-1)
> >
> > | or
> >
> > |> a(n) + b(n-2), a(n)+b(n-3), ... , a(n)+b(n-m)
> >
> > | or
> >
> > |> a(n-k) + b(n), ...
> >
> > The whole point is that we must remember only one position for each array
> > (k for A, and m for B). This is the position where it last-broke off its
> > stride.
> > The algorithm which I wrote doesn't do all this... I mean, my intent was
> > to do this, but the algo's not correct.. I guess I was too eager ...
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > On 4/3/06, Arunachalam <[EMAIL PROTECTED]> wrote:
> >
> > > Hi,
> > It is very hard for me to get the basic flow of this algorithm. Can
> > you explain the basic idea behind the algorithm.
> >
> > regards
> > Arunachalam.
> >
> >
> > On 4/3/06, Mayur < [EMAIL PROTECTED]> wrote:
> >
> > > right... that's correct. Arunachalam's right... Sorry... My second
> > attempt at it...
> >
> > One assumption, though - the output need not be sorted...
> >
> > 1: curMin <- min( a[0], b[0] ) - 1
> >
> > 2: i <- n, j<-n
> > 3: cnt <- 0, whoSurged = NONE;
> > 4: while ( cnt < n )
> > {
> > 5: output a[i] + b[j]
> > 6: cnt <- cnt + 1
> > 7: if a[i] + b[j] < curMin
> > 8: then if whoSurged == A
> > 9: then j <- j - 1
> > 10: i = n
> > 11:else i <- i - 1
> > 12:j = n
> > 12.5: curMin = min(a[0], b[0]) - 1
> > 13:goto step 4
> > 14: if (a[i-1] + b[j]) < (a[i] + b[j-1])
> > 15: then j <- j - 1
> > 16:if curMin == (min(a[0], b[0]) -1 )
> > 17:then whoSurged = B
> > 18:curMin = a[i-1] + b[j+1]
> > 19: else i <- i - 1
> > 20:if curMin == (min(a[0], b[0]) -1 )
> > 21: then whoSurged = A
> > 22: curMin = a[i+1] + b[j-1]
> > }
> >
> >
> >
> > On 4/3/06, iwgmsft < [EMAIL PROTECTED]> wrote:
> >
> > >
> > > assume we have set {ai+bj}.. of size n^2
> > >
> > > we can solve using MERGE-SORT i think.. to divide this problem into
> > > subproblems will take O(2logn) i.e. O(log n)...
> > > now at the time of merge it will take O(2n) i.e . O(n)... so this time
> > > we can find n largest values(by merging values in decending order)..
> > >
> > > correct me if i m wrong..
> > >
> > >
> > >
> > >
> > >
> >
> >
> > http"//ww.livejournal.com/users/arunachalam
> >
> >
> >
> >
> >
> > >
> >
>
>
> --
> ===
> want to know more about me
> http"//ww.livejournal.com/users/arunachalam
>
> --=_Part_4129_9059717.1144061235047
> Content-Type: text/html; charset=ISO-8859-1
> Content-Transfer-Encoding: quoted-printable
> X-Google-AttachSize: 11042
>
[algogeeks] Finding the distance between two permutations of a string of length N
Hi, I need to find distance between two permutations of a string of length N. Distance in this case is defined as the minimum number of swaps needed to convert one permutation into another. Can somebody help me out with it. The expected order of complexity is O(N.log(N)). Eg: With two permutations as : abcd, cdba . The distance is 3 as min 3 swaps are required to convert one into another. abcd(swap a and c) -> cbad(swap d and b) -> cdab(swap b and a)-> cdba --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
