## Google Interview Question

Software Engineers**Country:**United States

Previous comments are not entirely correct

- Assuming that the start & end node are adjacent to each other, not diagonal, and you can only move side to side, not diagonal, there is a solution if M is even or N is even, as LONG AS THE CELLS ARE CONTIGUOUS

IF M=2 or N=2 then you can have a scenario where the start & end cells split the space into 2 sides that are unreachable from each other

- If the start & end node are diagonal, then this is solveable as long as M is odd & N is odds, and you don't isolate one of the nodes in an unreachable corner

Should be pretty easy. And need to start from bottom left corner of the matrix

```
int main()
{
int matrix[4][4]={ {0, 0, 0, 0},
{0, 0, 0, 0},
{0, 1, 1, 1},
{0, 1, 1, 1},
};
int row = 3 ;
int col = 0;
int zero = 0;
while( col < 4 )
{
if( matrix[row][col] == 0 )
{
zero += ( row + 1 );
col++;
}
else
{
row--;
}
}
printf("Zero:%d\n", zero);
}
```

Here I suppose that we can only move left-right-bottom-up and not diagonally.

- emb May 24, 2016Such path exists if either M is even, or N is even. Suppose M is even. Then path is simple - begin from (0, 0), go down, then ascend in a snake-like manner, filling all cells. Since there are even number of rows, on the M-1 row we will go to the right, on M-2 to the left, ..., and on 0 - to the left back to (0, 0), since M - 2 is even.

Now - proof that if both coordinates are odd, there exists no such path.

Color all cells in a chess board manner. Since there are N*M cells, which is odd, it means that path from first cell to last cell through all cells will contain N*M - 1 moves, which is even. Each move changes color of current cell from black to white or vice versa. This means that first and last cells will be of the same color - this means that we will never be able to move from the last cell to the first in order to turn hamiltonian path into a cycle.