This is a Google interview question from careercup. Here is the original description,
"
There is a graph which has 1 source and 1 sink(destination node)
In between those 2 nodes there are n levels of nodes. At each level there are exactly m nodes.
Every node of level i is connected to every node of level i+1 (All edges go in forward direction)
Find total no. of paths between source and sink.
This was basic question. Then he tweaked it by adding few more edges.
Now there were some additional edges. Now sdges can go from any lower level to any higher level. That is not just from i to i+1..
can be from i to i+2 or i +3 so on...
(such bouncing edges were added only in the n levels not from or to (to src or sink)
Now find number of paths?
2. Analysis and Solution
It is very difficult to visualize it in mind until starting to drawing some diagrams with simple example first. Here I start from simple example and induce the general solution.
Take a look at the simple example n = 1, 2 with m nodes.
 |
| Level 1 and Level 2 (n = 1, 2) with nodes |
Take a look at the general example with n levels and m modes.
 |
| n levels and m nodes |
Take a look at the extra connection between any level.
 |
| A Jump Connection between Level i and Level j |
Summary of the solution:
- f(0) = 1
- f(1) = m
- f(n) = m*f(n-1) = pow(m, n);
- f(i, j) = f(i-1) * f(m-j) = pow(m, n+i-j-1), where i < j and i and j <= n.(a jump connection i, j)
