Google Interview Question
Country: United States
This is what I thought initially too. But I think this doesn't handle paths like this:
Consider 5 levels and 3 nodes per level (i.e. n = 5 and m = 3)
start ---> Choose one node from level 1 --> choose one node from level 4 --> sink
Can you check my answer and tell me I got it right? Thanks! :)
The answers are m^n and (m+1)^n respectively. It can be calculated by mathematical induction.
Part one: m^n
Part two: m^n + m^(n-1) + m^(n-2) + ... m^(n-n) .... (Mathematical induction)
Correcting this slightly
Part one: m^n
Part two: m^n + 2! x m^(n-1) + 3! x m^(n-2) + ... n! x m^(1)
The solution is Dynamic programming the you'll calculate the number of path from node i to the sick no suppose you are analysis a edge i -> j, here you have calculate from j to sink the the number of path from i to j is D[j], so the total number of path from i to sink is the sum of the path for all children of node i. Here is the code for a better understatement because my english is a mess lol.
int D[1000] Fill it with -1
int calc(int node){
if(node == sink) return 1;
if(D[node==-1]){
D[node] = 0;
for(over all children of node called next)
D[node] += calc(next);
}
return D[node];
}
the solution is calc(source)
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 :)
The answer will be -
m^2 + m^3 + m^4 + .... + m^n
How?
Let's consider the base case first -
n = 1, paths = m
n = 2, paths = m(m)
i.e. only possible paths are m*m
n = 3, paths = m(m + m(m))
i.e. we have three layers -
1. either directly reach the last layer (3nd layer) from first m nodes, paths = m*m
2. or reach via middle layer (1st layer), paths = m*m*m
so total paths = m*m + m*m*m
similarly, for n = 4
4 layers, 4 options
1. reach directly to 4th layer = m*m*m*m
2. reach via second last layer (3rd layer) = m*m*m
3. reach via second layer = m*m
total paths = m*m + m*m*m + m*m*m*m
Couldn't be problem attacked in the following way? :
There are N levels by M nodes each( for simplicity now I ignore source and sink levels ). So we have 2 ^ N - 1 possible ways to find a way between first and last level (no taking into account when path go only through nodes sink and source). For each combination of levels L, there are M^K ways to get node, where K is count of all set bits in L.So number of ways between first and last level would be : for (int l = 1; l< 2^n ;l++) sum+=m^k; where k is number of set bits in l. We now have to take into account sink and source nodes , which provides us addtional ways - > m^2*sum + 1 if n > 1 or m+1 if n = 1- this is total ways.
Couldn't be problem attacked in the following way? :
There are N levels by M nodes each( for simplicity now I ignore source and sink levels ). So we have 2 ^ N - 1 possible ways to find a way between first and last level (no taking into account when path go only through nodes sink and source). For each combination of levels L, there are M^K ways to get node, where K is count of all set bits in L.So number of ways between first and last level would be : for (int l = 1; l< 2^n ;l++) sum+=m^k; where k is number of set bits in l. We now have to take into account sink and source nodes , which provides us addtional ways - > m^2*sum + 1 if n > 1 or m+1 if n = 1- this
The second part can be solved with dinamic programming, i think this function does the job
long long int NumberOfWays(int n, int m, vector<pair<int, int> > edges){
vector<long long int> levels (n, 0);
sort(edges.begin(), edges.end());
v[0] = m;
int j=0;
for (int i=0;i<n-1;i++){
v[i+1] +=v[i]*m;
while(j<edges.size() and edges[j].first==i){
v[edges[j].second] += v[i]*m;
j++;
}
}
return v[n-1]*m;
}
long long int NumberOfWays(int n, int m, vector<pair<int, int> > edges){
vector<long long int> levels (n, 0);
sort(edges.begin(), edges.end());
v[0] = m;
int j=0;
for (int i=0;i<n-1;i++){
v[i+1] +=v[i]*m;
while(j<edges.size() and edges[j].first==i){
v[edges[j].second] += v[i]*m;
j++;
}
}
return v[n-1]*m;
}
Number of paths for part one = m ^ layers
Number of paths for part two = sum(i = 1 to layers) (m ^ i)
Where 'layers' is the number of layers considered i, i+1, etc
Edit:
The above approach is incorrect. After thinking about it some more, the actual count is
where n is the number of layers.
Which roughly means
m possible paths if the only middle layer is layer 'n'
m ( f(n - 1) ) possible paths if layer 'n' is considered part of the path in combination with all the other layers < n
f(n -1) possible paths if layer 'n' is not part of the path using all the other layers < n
This simplifies to
- zortlord August 28, 2015