cicciopuzzolo
BAN USER
Comments (3)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Part one is of course m^n.
Part two is sum_(i in 1..n)(m^i*(n choose n-i)).
Imagine paths that jump one level. The number of paths are in m^(n-1), but only for one level, hence you need to multiply by n (which is n choose 1).
Now imagine paths that jump two levels. The number of paths (if you fix which levels are being jumped) is m^(n-2), and this must be multiplied by the number of choices of the two levels to jump, that is n choose 2.
And so on and so forth :)
Comment hidden because of low score. Click to expand.
0
of 0 vote
I came independently to the same solution, except that I disagree on the complexity estimate: we have nm numbers, hence sorting them is inevitably O(nm*log(nm)), which trumps your ultimate estimate.
- cicciopuzzolo August 05, 2015Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Close, but not quite there. Check out my answer below.
- cicciopuzzolo August 29, 2015