## Google Interview Question for Software Engineer / Developers

• 0

Comment hidden because of low score. Click to expand.
3
of 3 vote

It's not a catalan number.

Obviously 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).

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

(p-1+q-1) items of which (p-1) are of one type and (q-1) are of another type. Straightway -

(p+q-2)!/((p-1)!(q-1)!)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Anonymous
Can you give me a function which calculate the number of paths?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ftfish is right...i think this question is too simple for GOOGLE

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

If the question is too simple for google then y r there so many different answers.

Comment hidden because of low score. Click to expand.
0

Because most programmers suck at combinatorics. ftfish has given the correct answer.

Comment hidden because of low score. Click to expand.
0

Can someone explain this?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

I agree it's too simple for Google. But the problem is that many people apply to Google, so a question like this might be appropriate to weed out a lot of folks ... say in a phone screen. And then you just gotta look at this thread to see why I'm right.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
}

Comment hidden because of low score. Click to expand.
0

p=1,q=100
do you really think there will be nearly 2^100 ways instead of only 1?

Comment hidden because of low score. Click to expand.
0

i updated the comment but it somehow did not reflect:

if(p<2 || q<2) return 1;
else return (2^(p-1)-1) + (2^(q-1)-1) - (2*abs(p-q));

Comment hidden because of low score. Click to expand.
0
of 0 vote

Any proof for this solution??
(2^(p-1)-1) + (2^(q-1)-1) - (2*abs(p-q))

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

No proof because it's just plain wrong.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

Comment hidden because of low score. Click to expand.
0

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];
}

Comment hidden because of low score. Click to expand.
0

when p=0 and q=0 it is returning 1?
Can you please check the code

Comment hidden because of low score. Click to expand.
0

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).

Comment hidden because of low score. Click to expand.
0

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];

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

According to the solution this comes out to be 3 but there are only 2 paths

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

This comes out to be 12 ways which I think is wrong.

Comment hidden because of low score. Click to expand.
0
of 0 vote

if(p==0 || q==0) return 0;
if(p==1 || q==1) return 1;
limit=((p-1)<(q-1))?(p-1):(q-1);
for(i=p-1+q-1,loop=1,dividend=divisor=1;loop<=limit;loop++,i--)
{
dividend*=i;
divisor*=loop;
}
return (dividend/divisor);

Comment hidden because of low score. Click to expand.
0
of 0 vote

If the Q is to Display all such path then?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Pascal Triangle, f(i,j)=f(i-1,j)+f(i,j-1); f(0,j)=1,f(i,0)=1;
so, f(N,N) is C(2*N, N)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote
Comment hidden because of low score. Click to expand.
0
of 0 vote

Assume 1 is going down and 0 is going right. Then ans is no. of ways to arrange (p-1)1s and (q-1)0s.

= fact(p+q-2)/(fact(p-1)*fact(q-1))

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

We have to go down q-1 level, and on each level we can choose a path from any of the p position, so if it is 2 rows 10 column array, we will have 10 different path, i.e rows -1 * no of columns.

So the different paths would be p*q-1.

Comment hidden because of low score. Click to expand.
0
of 0 vote

can't we say this?

we have two options at every point so it brings to nC2 and at last row we can not go down and at last coulmn we can not go right so it turns out to be

(p*q)C2 - p - q

correct me if i am wrong

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you give a function which prints all the possible paths from TopLeft to BottomRight

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can some give the java code for displaying all such paths

Comment hidden because of low score. Click to expand.
0
of 0 vote

<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>

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.