Google Interview Question Software Engineer / Developers
gud one..
Since we know the total no. of ways to go down there is only one way to go right, joining these down moves
Or we can think the other way --
if we know the total no. of ways to go right there is only one way to go down, joining these right moves
So we can say C(p-1+q-1,q-1)
That's the same thing.
why google asks such problem which related to some interesting 'catalan' number -- computable in linear time!
Of cors, DP works as well in O(pq) - quadratic time.
This problem is equivalent to arrange (p-1) Rs and (q-1) Ds. But it is not catalan number problem. Because Catalan has constrain that no initial segment should have more number of Rs than Ds. Ex arrangement of open and close brackets (no initial segment should have more number of closing bracket than opening brackets).
{}{} valid
}{ not valid
but we don't have any such constraint so its a simple combinatorial problem
will this answer will change, given one says min no of steps, otherwise useless question, I think min no of steps will be in only one way : All bottom then all right?
Out of (p-1)+(q-1) moves definitely there has to be (p-1) down moves. So, its just different ways of choosing the (p-1) from the (p-1)+(q-1). Thus, C( (p-1)+(q-1) , (p-1) ). Note that this is same as C( (p-1)+(q-1) , (q-1) ) had we chosen for picking the (q-1) right moves.
i tried to generalize the function by trial and error and assumed it to be true by induction. please give some test cases where it will fail:
int CountWays(int p, int q)
{
return (2^(p-1)-1) + (2^(q-1)-1) - (2*abs(p-q));
}
my idea was to sum up the combinations across each dimension. by that i mean, different ways in which u can take a turn along that dimension.
2*abs(p-q) was something that was used to fit more test cases
The number of solutions is isomorphic to the binomial expansion.
Let N(p,q) be the # of ways to go from top left to bottom right in a p X q matrix.
Clearly N(i,j)=0 if i<=0 or j<=0.
Also, as base cases N(1,1)=0, N(2,1)=1
Then in general N(p,q) = N(p-1,q) + N(p,q-1).
So this can be solved through recursion and counting the solutions.
int CountSolutions(int p,int q)
{
if (p<=0 || q<=0) return 0;
if (p==1 && q==1) return 1;
if ((p==2 && q==1) || (p==1 && q==2)) return 1;
return CountSolutions(p-1,q) + CountSolutions(p,q-1);
}
on the right track, not entirely correct. Try (2,3) you will see.
Correct way (0 based):
int Count(p,q)
{
if(p==0 || q==0) return 1;
return Count(p-1,q) + Count(p, q-1);
}
Optimized one
Count(p,q, a[,])
{
if(p == 0 || q ==0) return 1;
if(0 == a[p,q])
{
a[p,q] = Count(p-1,q, a) + Count(p, q-1, a);
}
return a[p,q];
}
this algorithm runs with exponential time complexity. It can be improved further to o(n+m) by using o(n+m) space (DP solution similar to 0-1 Knapsack).
Correction:- Time Complexity:- O(n*m) and Space Complexity:-O(n+m).
Possible solution:-
int[n][m] numWays = new int[n][m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if(i==0 && j==0){
numways[i][j] = 0;
} else if(i==0 || j==0) {
numways[i][j] = 1
} else {
numWays[i][j] = numWays[i][j-1] +
numWays[i-1][j];
}
}
}
return numWays[n-1][m-1];
Let us say its a matrix of size nxn, then should it not be 2+(n^2-2n+1)? Since we can only go right or down,the rightmost column will not create an extra path, once you reach the rightmost column you have to go down so you are merely continuing the path. Similarly for the bottommost row, once we hit that row we have no option but to go right (and hence continue the path which lead us to that row). So these elements dont add to the path counts. For all other elements, we can either go right or go down (i.e. continue the path or change the path and hence add 1 to the count of paths). So each of these elements kind of forks the execution. Also, the first 2 is for the upper left element (Starting point). It adds 2 to #paths where as others add at the most 1 to the count. Please correct me if I am wrong.
the task is not just to reach the bottom, but the rightmost bottom.
c'mmon the answer is simple : it is just factorial((p-1)+(q-1)). if u want to write a function , then just add some boundary checks as well.
int CountSolutions(int p,int q)
{
if (p<=0 || q<=0) return 0;
if (p==1 || q==1) return 1;
if (p==2) return q;
if (q==2) return p;
return CountSolutions(p-1,q) + CountSolutions(p,q-1);
}
This looks correct, but has a common efficiency bug. You are repeating a lot of shared work between CountSolutions(p-1,q) and CountSolutions(p,q-1). What you need to do is cache the results of calls to CountSolutions and then look up that cache when you need the results to sub-problems. This technique is called memoization.
I won't mention anything about avoiding this function in the first place via combinatorics because that's math. But CS-wise this can be improved.
public static void main(String[] args)
{
final int MAX_ROW = 6;
final int MAX_COL = 5;
System.out.println(countPath(0,0,MAX_ROW-1, MAX_COL-1, MAX_ROW, MAX_COL));
}
private static int countPath(int bR, int bC, int eR, int eC, int maxR, int maxC)
{
if((bR==eR )&& (bC == eC))
{
return 1;
}
else if((bR >= maxR) || (bC >= maxC))
{
return 0;
}
else
{
return countPath(bR+1, bC, eR, eC, maxR, maxC)+
countPath(bR, bC+1, eR, eC, maxR, maxC);
}
}
<pre lang="" line="1" title="CodeMonkey50584" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static int nways;
public static void main (String[] args) throws java.lang.Exception
{
String str = "";
count(2,2, str);
System.out.println("count: " + nways);
}
public static void count(int r, int d, String str){
if((r==0) && (d==0)){
++nways;
System.out.println(str);
}
else if((r==0)){
count(r,d-1,str + "d");
}
else if((d==0)){
count(r-1,d,str + "r");
}
else {
count(r-1, d, str + "r");
count(r, d-1, str + "d");
}
}
}
</pre><pre title="CodeMonkey50584" input="yes">
</pre>
It's not a catalan number.
- ftfish July 21, 2010Obviously there're (p-1)+(q-1) moves to make and p-1 of them are "go down".
So the answer is just C(p-1+q-1, p-1).