Interview Question
Country: United States
I assume that you can traverse the matrix in up, down, left and right direction.
Say that starting point A has coordinates A(r, c)
Check if any of neighboring points is equal 1
- up A(r-1, c)
- down A(r+1, c)
- left A(r, c -1)
- right A(r, c +1)
If any of this points is equal 1 invoke the method recursively with new coordinates eg new starting point is (r-1, c).
Repeat the process till you reach destination point or matrix's borders.
Simple code:
package interview;
public class FindPath {
public static void main(String[] args) {
int[][] m = { { 1, 0, 0, 0, 1 }, { 1, 0, 0, 0, 0 }, { 1, 1, 0, 0, 0 }, { 0, 1, 1, 1, 0 }, { 0, 0, 0, 1, 1 } };
System.out.println("Found path: " + findPath(0, 0, m.length - 1, m[0].length - 1, m));
}
private static boolean findPath(int startRow, int startCol, int endRow, int endCol, int[][] m) {
if (startRow < 0 || startCol < 0 || endRow < 0 || endCol < 0 || startRow > m.length - 1
|| startCol > m[0].length - 1 || endRow > m.length - 1 || endCol > m[0].length - 1) {
return false;
}
if (startRow == endRow && startCol == endCol) {
return true;
}
m[startRow][startCol] = -1;
// go up
boolean up = false;
if (startRow - 1 >= 0 && m[startRow - 1][startCol] == 1) {
up = findPath(startRow - 1, startCol, endRow, endCol, m);
}
// go down
boolean down = false;
if (startRow + 1 <= m.length - 1 && m[startRow + 1][startCol] == 1) {
down = findPath(startRow + 1, startCol, endRow, endCol, m);
}
// go left
boolean left = false;
if (startCol - 1 >= 0 && m[startRow][startCol - 1] == 1) {
left = findPath(startRow, startCol - 1, endRow, endCol, m);
}
// go right
boolean right = false;
if (startCol + 1 <= m[0].length - 1 && m[startRow][startCol + 1] == 1) {
right = findPath(startRow, startCol + 1, endRow, endCol, m);
}
return up || down || right || left;
}
}
You can also read about flood fill algorithm.
This is typically known as Percolation problem and widely used real life computing problems such electronics circuits,
Flow of fluid etc.
Now how do we correlate with what question is where ever there are 1's means its open site and keep moving till we find target through the 1's
Ways to solve this -
1) QuickUnion Algorithm
}
- nirdosh.chouhan December 16, 2013This will find the path in linear time.
More details can be found at - Search Quick Union Find