CareerCup

It is a two dimension dp problem.

sorry, the robot has to start in upper left and get to the bottom right square. Interviewer wanted an algorithm to compute the number of paths, rather than just coming up with a mathematical answer. She also seemed pleased that my solution provided not only the number of paths, but the paths themselves.

A robot can take path (N,M) from either (N-1,M) or (N,M-1)
if N and M is 0, its the beginning so return 0.
if N or M is 0, we can get there in 1 path.

We call paths(N,M) with s[][] initialized to -1.

int paths(int i,int j)
{
if(!(i||j))
return 0;

if(!(i&&j))
return 1;

if(s[i][j] != -1)
return s[i][j];

s[i][j] = paths(i-1,j) + paths(i,j-1);

return s[i][j];
}

# assume maze_env is an object that knows
# all about the geometry of the maze,
# end point is (0,0)

# maze_env defined somewhere above
paths_cache = {}
def get_maze_paths(x, y):
  # retrieve memoized solution
  if (x,y) in paths_cache:
    return paths_cache((x,y))
  if x, y == 0, 0:
    return []
  if x and maze_env.can_go_right(x, y):
    right_maze_paths = get_maze_paths(x-1, y)
  if y and maze_env.can_go_down(x, y):
    down_maze_paths = get_maze_paths(x, y-1)
  maze_paths = [['R'] + path for path in right_maze_paths + ...
                ['D'] + path for path in down_maze_paths]
  # memoize solution for (x,y)
  paths_cache[(x,y)] = maze_paths
  return maze_paths

Is there an API that tells me where are the walls?
Do you want to go from top-left to bottom right?
...

int paths(int m, int n)
{
    int sum=0;
    int i;

    if(!(m || n)) 
    {   
        return 0;
    }   

    if(m == 1)
    {   
        return n + 1;
    }   

    if(n == 1)
    {   
        return m + 1;
    }   

    for(i = 0; i <= n; i++)
        sum += paths(m - 1, n - i); 

    return sum;
}

first fill first row and first column as 0 1 1 1.. as for 1st row only way to reach a column is by moving to right -> so and for column moving down from previous column

now for(i=1;i<n;i++)
for(j=1;j<m;j++)
a[i][j]=a[i-1][j]+a[i][j-1];

a[n][m] gives the ways to reach that box in matrix.

isn't it
(m+n) choose n?

As one said above, this is a 2 dimensional dp question (Actually very typical).
So if you use recursive, that's probably not a good answer...Scan the matrix row by row will be better, and will also reduce the use of space since you only need two rows, rather than the whole matrix to save the temporary result.

its foolish to find all the paths. Since the number of paths would be exponential if the maze was randomly generated. How come the interviewer was impressed when you decided to store all paths.Wish the interviewers are not so dumb. Rather than that it would have been better if you were asked to print only 1 path.

its foolish to find all the paths. Since the number of paths would be exponential if the maze was randomly generated. How come the interviewer was impressed when you decided to store all paths.Wish the interviewers are not so dumb. Rather than that it would have been better if you were asked to print only 1 path.

#include <iostream>
void PrintRobotPaths(std::string path, int row, int column, int totrows, int totcols)
{
	if(column == totcols && row == totrows)
	{
		std::cout << path << std::endl;
		return;
	}
	if(row == totrows)
	{
		std::string pc = path + " D";
		PrintRobotPaths(pc, row, column+1, totrows, totcols);
		return;
	}
	if(column == totcols)
	{
		std::string pr = path + " R";
		PrintRobotPaths(pr, row+1, column, totrows, totcols);
		return;
	}
	std::string pr = path + " R";
	std::string pc = path + " D";
	PrintRobotPaths(pr, row+1, column, totrows, totcols);
	PrintRobotPaths(pc, row, column+1, totrows, totcols);
}

int main(int argc, char** argv)
{
	int row=4;
	int column=4;
	std::string path;
	PrintRobotPaths(path,1, 1, row, column);
	return 0;
}

No of paths: (n+m)! / n!.m!

Here is one way to do it.

public static void displayAllPaths(final int rows, final int columns, int curRow, int curCol, char[] path) {
        if (curRow == rows - 1 && curCol == columns - 1) {
            for (int i = 0; i < path.length; i++) {
                System.out.printf("%3c", path[i]);
            }
            System.out.println();
            return;
        }

        if (curCol < columns - 1) {
            path[curRow + curCol] = 'R';
            displayAllPaths(rows, columns, curRow, curCol + 1, path);
        }

        if (curRow < rows - 1) {
            path[curRow + curCol] = 'D';
            displayAllPaths(rows, columns, curRow + 1, curCol, path);
        }
    }