## Google Interview Question for Software Engineers

• 0

Country: United States

Comment hidden because of low score. Click to expand.
5
of 5 vote

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

Such 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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

The Start cell can be anywhere or is always located at 0,0; Can you clarify next cell to the start node I mean is right and left or could be any of the 8 cells surrounding it ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

The answer would depend on whether or not one allows diagonal segments, such as a segment (0,0) -> (1,1) If you do not allow this parity arguments come into play.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

Pollllklkk,m. Jjj. B. M n. Mbbbbgyghnmk,l..l mm. ...

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think that next to start node doesn't mean to be diagonal

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this not travelling salesman problem ?

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````//this appears some kind of brain teaser, you can draw such a path for any M>1 and N>1
static boolean checkSpanningPath(int M,int N)
{
return M>1 && N>1;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.