Google Interview Question Software Engineer / Developers
Country: United States
your state in DP would be the whole grid because it's not enough to know which node you are at right now, but you need to know the state of your board
why not DFS variant where you modify rule of visited marking?
Thanks for suggesting this approach.Here is the code:
typedef struct point point;
#include <stdio.h>
#define SIZE 4
struct point {
int i;
int j;
struct point *next;
};
typedef struct point point;
void push(point **last, int i, int j)
{
/* base case when stack is empty */
if(*last == NULL) {
point *temp = malloc(sizeof(*temp));
temp->i = i;
temp->j = j;
temp->next = NULL;
*last = temp;
} else {
point *temp = malloc(sizeof(*temp));
temp->i = i;
temp->j = j;
temp->next = *last;
*last = temp;
}
}
point *pop(point **last)
{
point *temp = *last;
*last = (*last)->next;
return temp;
}
int stack_empty(point *last)
{
if(last == NULL)
return 1;
else
return 0;
}
int dfs(int mat[SIZE][SIZE], int i, int j, point **last)
{
int count = 0;
if(mat[i][j] == 0)
return 0;
/* push 0,0 on the stack */
push(last, 0, 0);
while(!stack_empty(*last)) {
point *co = pop(last);
if(co->i == SIZE-1 && co->j == SIZE-1)
count++;
/* check for neigbours of x*/
if(co->j +1 < SIZE && mat[co->i][co->j+1] == 1) {
push(last, co->i, co->j+1);
}
if(co->i+1 < SIZE && mat[co->i+1][co->j] == 1) {
push(last, co->i+1, co->j);
}
}
return count;
}
int main()
{
point *last;
last = NULL;
int mat[SIZE][SIZE] = {
1, 1, 1, 1,
1, 1, 1, 1,
1, 0, 0, 1,
1, 1, 1, 1,
};
printf("%d\n", dfs(mat, 0, 0, &last));
}
are you sure your count works? at the end I'll get the total number of ways to exit the maze?
Your code does not work with this example :
int mat[SIZE][SIZE] = {
1, 1, 1, 0, 1,
1, 0, 1, 0, 1,
1, 0, 1, 1, 1,
1, 0, 0, 0, 0,
1, 0, 0, 0, 0,
};
The reason is you are not accounting for decrementing of the indices.
@try,. I am not sure about your answer. If you follow 1's, there is path from 0,0 to N,N.
Does not work for this input.
int mat[SIZE][SIZE] = {
1, 1, 1, 1,
1, 1, 0, 0,
1, 0, 1, 1,
1, 1, 1, 1,
};
This is a DP problem. At each node you can think of path covered so far and the optimal solution to reach the end from here. Without recursion also gives a hint that DFS is not the answer. Look for min cost path problem in DP section at geeksforgeeks for a variation to this problem.
the min cost path problem is completely different
here there is no optimization being made, they just want all possible paths
DFS is the way to go where visited is reset after we are done with node
@Anon : You could use DFS dear friend, point I am making is don't optimize in DP but get rid of the 1's that will also solve the problem.
To me I see that DP would only make sense to me if you could only walk down, to the right and diagonally to the right.
The problem with DP here is that there is no substructure since the substructures are dependent.
This is what makes it so different than min cost path.
If you think it could be done using DP, please explain some more what your state in DP would be and also the problem and the subproblems...
PATH array stores 1 if there exists a path from i,j to N,M using only rightward and downward directions else 0
Initialize PATH to all zeros.
PATH[N-1][M-1] = 1;
for i in N-1 to 0:
for j in M-1 to 0:
if(i<N-1):
PATH[i][j] = PATH[i+1][j];
if(j<M-1):
PATH[i][j] = PATH[i][j] | PATH[i][j+1];
PATH[i][j] = PATH[i][j] & bool[i][j];
check PATH[0][0];
The same logic can be easily extended to store num of paths at i,j. Path[i][j] = Path[i+1][j] + Path[i][j+1];
int isValid(int i,int j,int n,int m,int arr[4][4])
{
if(i >= n || j >=m || i <0 || j < 0 )
return 0;
if(arr[i][j] != 0)
return 0;
return 1;
}
int number_ways(int arr[4][4],int n,int m)
{
int i =0,j=0,dirTried =0;
int count =0;
int val =0;
// arr[i][j]=0;// a value has 2 kinds of information stored in it. previous index and the number of directions it has travelled so far.
while(true)
{
int ti = i , tj = j;
// get number of directions tried for that number
dirTried = arr[ti][tj]/(n*m);
switch (dirTried)
{
case 0:
ti = ti + 1;
break;
case 1:
tj = tj +1;
break;
case 2:
ti = ti - 1;
break;
case 3:
tj = tj - 1;
break;
case 4:
val = arr[i][j] %(n*m) ;
i = val /n;
j = val %m;
if( i==0 && j==0)
return count;
arr[ti][tj] = 0;
break;
}
if(dirTried ==4)
continue;
arr[i][j] = arr[i][j]+(n*m);
if(isValid(ti,tj,n,m,arr))
{
if( ti == n-1 && tj == m-1)
{
count++;
continue;
}
arr[ti][tj] = i*n + j ;
i =ti;
j= tj;
}
}
return count;
}
int main()
{
int arr[4][4] = {{ 0 ,-1,-1,0},{0,0,0,0},{0,-1,0,0},{0,0,0,0}};
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
cout<< arr[i][j] << " ";
cout<<"\n";
}
int count = number_ways(arr,4,4);
cout<<count;
cin>>count;
return 0;
}
Can someone please provide me a DP solution here
I am not able to make the recursive optimal substructure to it.
I have a variation of the program already written.
Run it.
Here F = 1, means dead end path.
This is recursive convert to DP.
public class printPossiblePathsInMatrix {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
char[][] arr = new char[][]{
{'A','B','F'},
{'C','D','F'},
{'E','G','H'}
};
possiblePath("", arr, 0, 0);
}
private static void possiblePath(String str, char[][] a, int r, int c)
{
if(r > 2 || c > 2)
return;
if(r==2 && c==2){
str+= a[r][c];
System.out.println("---" + str);
return;
}
if(c+1 < 3)
if(a[r][c+1] != 'F'){
String s1 = str + a[r][c];
possiblePath(s1, a, r, c+1);
}
if(r+1 < 3)
if(a[r+1][c] != 'F'){
String s2 = str + a[r][c];
possiblePath(s2, a, r+1, c);
}
if( r+1 < 3 && c+1 < 3)
if(a[r+1][c+1] != 'F'){
String s3 = str + a[r][c];
possiblePath(s3, a, r+1, c+1);
}
}
}
It can be solved with dynamic programming. Assuming that you can move either right or down which can be a good point to discuss with interviewer. Also this is recursive solution.
Suppose you are at position N, M you can come to it either by N-1, M or by N, M-1. This way we can work upwards to find total no of ways.
static int total_ways = 0;
class Point{
int x,
int y,
Point(int a, int b)
{
x = a;
y = b;
}
boolean getPath(int x, int y, ArrayList<Point> path, Hashtable<Point, Boolean> cache)
{
Point p = new Point(x, y);
if(cache.containsKey(p))
{
return cache.get(p);
}
path.add(p);
if(x == 0 && y == 0)
{
total_ways++;
return true;
}
boolean success = false;
if(x >= 1 && isFree(x - 1, y)
{
success = getPath(x - 1, y, path, cache);
}
if(!success && y >= 1 && isFree(x, y - 1))
{
success = getPath(x, y - 1, path, cache);
}
if(!success)
{
path.remove(p);
}
cache.put(path, success);
return success;
}
This is a non-recursive solution that uses backtracking. It simulates what most humans would do in a maze. You leave breadcrumbs, go as far as you can, and when you hit a dead end, pick up the last breadcrumb and try a new direction.
# This is an iterative solution for traversing a maze. We try
# to extend our path as long as we can, but then backtrack
# when we hit a dead end or solution.
def solve(maze):
num_solutions = 0
traversal = {}
traversal['directions'] = ''
traversal['point'] = (0, 0)
endpoint = (len(maze)-1, len(maze[0])-1)
forbidden = ''
while True:
new_traversal = extend_traversal(maze, traversal, forbidden)
if not new_traversal:
if traversal['directions'] == '':
print 'NO MORE OPTIONS'
break
traversal, forbidden = backtrack(maze, traversal)
continue
forbidden = ''
traversal = new_traversal
r, c = traversal['point']
if (r, c) == endpoint:
print 'solution:', traversal['directions']
num_solutions += 1
return num_solutions
def extend_traversal(maze, t, forbidden):
new_t = {}
r, c = t['point']
if 'D' not in forbidden:
if can_go_down(maze, r, c):
new_t['directions'] = t['directions'] + 'D'
new_t['point'] = (r+1, c)
maze[r+1][c] = 2
return new_t
if 'U' not in forbidden:
if can_go_up(maze, r, c):
new_t['directions'] = t['directions'] + 'U'
new_t['point'] = (r-1, c)
maze[r-1][c] = 2
return new_t
if 'R' not in forbidden:
if can_go_right(maze, r, c):
new_t['directions'] = t['directions'] + 'R'
new_t['point'] = (r, c+1)
maze[r][c+1] = 2
return new_t
if 'L' not in forbidden:
if can_go_left(maze, r, c):
new_t['directions'] = t['directions'] + 'L'
new_t['point'] = (r, c-1)
maze[r][c-1] = 2
return new_t
return None
def backtrack(maze, t):
new_t = {}
last_dir = t['directions'][-1]
r, c = t['point']
maze[r][c] = 0
new_t['directions'] = t['directions'][:-1]
if last_dir == 'D':
new_t['point'] = (r-1, c)
return new_t, 'D'
if last_dir == 'U':
new_t['point'] = (r+1, c)
return new_t, 'DU'
if last_dir == 'R':
new_t['point'] = (r, c-1)
return new_t, 'DUR'
if last_dir == 'L':
new_t['point'] = (r, c+1)
return new_t, 'DURL'
def can_go_left(maze, r, c):
return c-1 >= 0 and maze[r][c-1] == 0
def can_go_right(maze, r, c):
return c+1 < len(maze[0]) and maze[r][c+1] == 0
def can_go_down(maze, r, c):
return r+1 < len(maze) and maze[r+1][c] == 0
def can_go_up(maze, r, c):
return r-1 >= 0 and maze[r-1][c] == 0
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 1, 0],
]
num_solutions = solve(maze)
print num_solutions
dfs:
#include<iostream>
#include<stack>
using namespace std;
struct Pos
{
int r;
int c;
bool visited;
int neighbor;
};
int neighbor_r[4]={0,1,0,-1};
int neighbor_c[4]={-1,0,1,0};
int MazeWalk(bool* maze,int row,int col)
{
int res=0;
vector<vector<Pos>> rec;
rec.resize(row);
for(int i=0;i<row;i++)
{
rec[i].resize(col);
for(int j=0;j<col;j++)
{
Pos my_pos;
my_pos.r=i;
my_pos.c=j;
my_pos.visited=maze[i*col+j];
my_pos.neighbor=0;
rec[i][j]=my_pos;
}
}
stack<Pos> my_stack;
rec[0][0].visited=true;
my_stack.push(rec[0][0]);
while(!my_stack.empty())
{
Pos& cur_pos=my_stack.top();
int cur_r=cur_pos.r,cur_c=cur_pos.c;
//cout<<cur_r<<" "<<cur_c<<" "<<cur_pos.neighbor<<endl;
if(cur_r==row-1 && cur_c==col-1)
{
res++;
rec[cur_r][cur_c].visited=false;
my_stack.pop();
continue;
}
if(cur_pos.neighbor>=4)
{
rec[cur_r][cur_c].visited=false;
my_stack.pop();
continue;
}
int new_r,new_c;
new_r=cur_r+neighbor_r[cur_pos.neighbor];
new_c=cur_c+neighbor_c[cur_pos.neighbor];
cur_pos.neighbor++;
if(new_r>=0 && new_c>=0 && new_r<row && new_c<col && rec[new_r][new_c].visited==false)
{
rec[new_r][new_c].visited=true;
my_stack.push(rec[new_r][new_c]);
}
}
return res;
}
Like some of the earlier comments, I believe this can be solved using dynamic programming. Assuming we can either go right or go down from [0][0], p[i][j], the # of paths from [i][j] to [N][M], can be computed as follows.
temp = 0;
if (i + 1 <= N && m[i + 1][j] == 0) temp += p[i + 1][j]; // down
if (j + 1 <= M && m[i][j + 1] == 0) temp += p[i][j + 1]; // right
p[i][j] = temp;
One special case is p[N][M]:
if (m[N][M] == 0) p[N][M] = 1; else p[N][M] = 0;
Then,
for (i = N; i >= 0; i--)
for (j = M; j >= 0; j--)
if (m[i][j] == 0) compute p[i][j] as mentioned above;
After the computation, p[0][0] should be the # of possible paths from [0][0] to [N][M].
If the maze paths are indeed constrained to only go right and down, then this is a classic DP problem. If not, check out the solution that starts "This is a non-recursive solution that uses backtracking." for a recursive solution that allows for a more realistic maze with spirally paths around the obstacles.
The condition in this problem is not enough. If the walking ways are limited to right and down, it can be achieved by DP, where M[i][j] = M[i+1][j] + M[i][j+1]. However, if it is allowed to walk in all direction, it would be solved by DFS with a visited history of all points, which is analog to a brutal force algorithm.
just do a DFS using Stacks
- Anonymous February 17, 2013