Google Interview Question
SDE1sCountry: United States
nope not really efficient at all .. try using BFS from starting point pretty simple question
Nice precise and intuitive solution +1 :-)
@krr.ashish: I do not understand why you said that this solution is not efficient 'at all'. Could you please elaborate?
Output will be 2.. Which I suppose is correct.
1st Path : 4th row and 1st column
2nd Path : 4th Column and 1st row.
What other paths do you see? Elaborate.
//Using DP
int a[m][n];
int paths[m][n] = {0};
for(i=0; i<m; i++) {
for(j=0; j<n; j++) {
if(i==0 && j==0) {
paths[i][j] = 1;
continue;
}
if(a[i][j] == 0)
paths[i][j] = 0;
else
paths[i][j] = (i-1 >=0?paths[i-1][j]:0) + (j-1>=0?paths[i][j-1]:0);
}
}
printf("Number of paths = %d\n", paths[m-1][n-1]);
Convert the matrix to a DAG: each '1' cell makes a vertex, which is connected to its right/down neighbors (if exist). There are no back edges (cycles), because we're not allowed to go up or left - hence we have a DAG. This is good, because there are polynomial algorithms for finding all paths between two nodes in a DAG:
the idea resembles DP, where in each step we build on top of the previous ones. we'll compute the number of distinct paths from a given node to the target node by summing up the paths counters of its descendants. we start from the nodes directly connected with the target node and go backwards till we get to the source. the easiest way for verifying that we only process a node after all its children are processed is to run first a topological sort and then process the nodes in a topological reverse order.
public class FindPath {
/**
* @param args
*/
int m=5;
int n=5;
static int count=0;
public static void main(String[] args) {
FindPath fp=new FindPath();
int arr[][]=new int[][]{{1,0,1,0,0},{1,0,0,1,1},{1,1,1,1,1},{0,1,1,1,1},{1,1,0,0,1}};
fp.findPaths(arr,0,0,"");
System.out.println("Total Path : "+count);
}
private void findPaths(int[][] arr, int i, int j, String path) {
path=path+" ("+i+","+j+")";
if(i==(m-1) && j==(n-1))
{
System.out.println(path);
count++;
return;
}
if(i<(m-1) && arr[i+1][j]==1)
{
findPaths(arr, i+1, j, path);
}
if(j<(n-1) && arr[i][j+1]==1)
{
findPaths(arr, i, j+1, path);
}
return;
}
}
public void PathArray()
{
int[,] ipmatrix = new int[4, 4] { { 1,1,0,0 }, { 1,1,1,0}, {0,1,1,0}, { 1,0,1,1} };
int rowlen=ipmatrix.GetLength(0);
int collen=ipmatrix.GetLength(1);
int count = 0;
count= wrapperpatharray(ipmatrix, 0, 0, rowlen, collen);
}
public int wrapperpatharray(int[,] ip,int i,int j, int rowlen, int collen)
{
if (i == rowlen - 1 && j == collen - 1)
{
Console.WriteLine("Pathfound");
return 1;
}
if (i > rowlen - 1 || j > collen - 1)
return 0;
if (ip[i, j] == 0)
return 0;
return( wrapperpatharray(ip, i, j + 1, rowlen, collen)+
wrapperpatharray(ip, i + 1, j, rowlen, collen));
}
///
function numberOfPaths(arr) {
// Assume each row has the same number of arguments
var M = _array.length;
var N = _array[0].length;
var pathCount = 0;
var x = 0;
var y = 0;
findPath(arr, x, y, M, N);
console.log(pathCount + " paths found!");
function findPath(a, x, y, rows, cols) {
if (a[y][x]) {
// Check end condition
if (y == rows-1 && x == cols-1) {
pathCount++;
}
if (x+1 < cols) {
// Check right
findPath(a, x+1, y, rows, cols);
}
if (y+1 < rows) {
// Check down
findPath(a, x, y+1, rows, cols);
}
}
else {
console.log("Dead end ("+y+", "+x+")");
}
}
}
\\\
package test;
public class ArrayPath {
private int totalNumberOfPath = 0;
public int numberOfPaths(int[][] array) {
if (array[0].length == 0 || array.length == 0) {
return -1;
}
findPath(array,0,0);
return totalNumberOfPath;
}
private void findPath(int[][] array, int posX, int posY) {
if (posX == array[0].length - 1 && posY == array.length -1) {
totalNumberOfPath++;
return;
}
if (posX+1 < array[0].length && array[posY][posX+1] == 1) {
findPath(array, posX+1, posY);
}
if (posY+1 < array.length && array[posY+1][posX] == 1) {
findPath(array, posX, posY+1);
}
return;
}
public static void main(String argv[]) {
ArrayPath arrayPath = new ArrayPath();
int[][] array = {{1, 1, 1, 1},
{1, 1, 1, 1},
{1, 0, 1, 1}};
System.out.println(arrayPath.numberOfPaths(array));
}
}
#include <stdio.h>
int count=0;
int maxrows = 10;
int maxcols = 10;
int M, N;
void DFS (int array[][10], int x, int y)
{
int r, c;
/* process element at input row and column */
if (array [x][y]==0 || x>M || y>N){
/* no path forward; return */
return;
}
if (x==M-1 && y==N-1){
/* found path; increment count */
count++;
return;
}
/* recurse: to matrix starting from same row, next column */
r = x;
c = y +1;
if (c < N-1) {
DFS (array, r,c);
} else {
/* if last column - check to see */
/* if rest of rows in last column allow for a path */
int tr = r;
while ( tr <= M-1) {
if (array[tr][c] == 1) {
tr++;
}
else {
return;
}
}
/* reached last node - path exists! */
count++;
}
/* recurse: to matrix starting from next row, same column */
r = x+1;
c = y;
if (r < M-1) {
DFS (array, r,c);
} else {
/* if last row - check to see */
/* if rest of columns in last row allow for a path */
int tc = c;
while ( tc <= N-1) {
if (array[r][tc] == 1) {
tc++;
} else {
return;
}
}
/* reached last node - path exists! */
count++;
}
}
int main () {
int i, j;
scanf("%d %d",&M,&N);
int a[10][10] = {};
int row, col;
for(i=0;i<M;i++)
for(j=0;j<N;j++)
scanf("%d", &a[i][j]);
if ((M > maxrows) || (N > maxcols)) {
printf("max of 10 rows and 10 cols allowed for input\n");
return (-1);
};
/* print input matrix */
for(row=0;row<M;row++) {
for(col=0;col<N;col++){
printf("%d ",a[row][col]);
}
printf(" EOR\n");
}
DFS(a,0,0);
printf("number of paths is %d\n", count);
return 0;
}
We can solve the above problem using recursion with backtracking.
We start by moving from the bottom-right cell that is (m-1,n-1). We can move either left or top from each cell. Recursively call the findPath function with left cell and top cell. If you encounter a 0 at a cell position, discard that path. When we reach the (0,0) cell, increment the count variable.
Keep a count variable that keeps track of all the possible path.
Code :
- Coder January 27, 2014