www.google.com Mountain View, CA 5000+ Employees
Work in HR? Complete Your Profile

# Interview Question for Software Engineering Intern at Google: Apr 18, 2012

## Write an algorithm to calculate the total number of paths possible from point (0, 0) to point (m, n) in an m by n grid. (You cannot retrace a line you already made when forming a path.)

Yes | No
Inappropriate?

1 of 1 people found this helpful

Apr 28, 2012
Classic recursion problem:

int CalcPaths(int nXPos, int nYPos, int M, int N)
{
if(nXPos > M || nYPos > N)
{
return 0;
}

if(nXPos == M && nYPos == N)
{
return 1;
}

return CalcPaths(nXPos+1, nYPos, M, N) + CalcPaths(nXPos, nYPos + 1, M, N);
}
Yes | No
Inappropriate?

Apr 30, 2012
Use dynamic programming to process the problem bottom up, that will significantly reduce the redundant computation effort. The basic idea is same as the recursive method.
Yes | No
Inappropriate?

2 of 2 people found this helpful

May 30, 2012
the above method only works when it can not go left or top.