Punit2012
BAN USER- 1of 1 vote
AnswersYou are given a matrix of size M rows and N columns. A is the first element i.e. mat[i][j] where i=j=0, and B is the end point i.e. i=M and j=N. There is a robot at A and it can only move one step right or go down one step. There are walls in the matrix denoted by X. The robot cant make his move when it encounters a wall on right or on its way down. Find the number of paths from starting point A to the end point of the matrix B for the robot.
- Punit2012
hint:recursion with condition checking for the end point and the wall.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
it is recursion, so it definitely would be DFS and not BFS. you have to call recursion starting at the node and continue till you get to the end point B. every time you call recursion, you would check if you can go right or down (you would need a function for doing that). If yes, go right or go down and again call recursion. You have to store the current node into an array for keeping track of the possible path. if you dont find a path from that node, remove it from the array. continue till recursion ends for each node. you would also need a counter which would increase every time you find a path. return this at the end.
- Punit2012 May 02, 2010you are making it complicated. Just copy one block to another. memcpy would not be the right answer as it would not take care if the pointers to both the block point at same location, so the right answer would be memmove which would ensure that the location of both the blocks are not same. did you now get it??
- Punit2012 May 02, 2010
memmove does not use a buffer. the answer to the question had to take care of the overlapping memory blocks. below is the code to implement memmove which I wrote during the interview:
- Punit2012 May 03, 2010void memmove(char **blockA, char **blockB, int N)
{
if(*blockA==*blockB)
{
//do nothing
}
if(*blockA!=blockB)
{
if(*blockA>*blockB)
{
if(*blockA>*blockB)
int temp=blockA-blockB;
for(int i=temp; i<N+temp;i++)
{
*blockB[i-temp]=*blockA[i-temp];
}
else
{
temp=blockB-blockA;
for(i=N+temp;i>temp;i--)
{
*blockB[i-temp]=*blockB[i-temp];
}
}
}
}
}