[Recursion and Dynamic Programming] interview questions #2

[rygh4775]

Robot in a Grid: Imagine a robot sitting on the upper left corner of grid with r rows and c columns. The robot can only move in two directions, right and down, but certain cells are "off limits" such that the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to the bottom right.

[rygh4775]

Approach

To find a path from the origin, we just work backwards like this. Starting from the last cell, we try to find a path to each of its adjacent cells.

Solution

/* 
input example:
boolean[][] maze = new boolean[3][3];
maze[0][0] = true; maze[1][0] = false; maze[2][0] = false;
maze[0][1] = true; maze[1][1] = false; maze[2][1] = false;
maze[0][2] = true; maze[1][2] = true; maze[2][2] = true;
*/

ArrayList<Point> getPath(boolean[][] maze) {
    if(maze == null | maze.length == 0 ) return null;
    ArrayList<Point> path = new ArrayList<>();
    if(getPath(maze, maze.length -1, maze[0].length -1, path)) {
        return path;
    }
    return null;
}

boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path) {
    /* If out of bounds or not available, return. */
    if(col < 0 || row < 0 || !maze[row][col]) {
        return false;
    }

    boolean isAtOrigin = (row == 0) && (col == 0);

    /* If there's a path from the start to here, add my location. */
    if(isAtOrigin || getPath(maze, row, col -1, path) || getPath(maze, row-1, col, path)) {
        Point point = new Point(row, col);
        path.add(point);
        return true;

    }

    return false;
}

Time complexity

O(2^r+c), r+c is a length of the path.

Space complexity

O(r+c), r+c is a length of the path.

[rygh4775]

Approach

To avoid finding duplicate path, we should remember that already visited.

Solution

ArrayList<Point> getPath(boolean[][] maze) {
    if(maze == null | maze.length == 0 ) return null;
    ArrayList<Point> path = new ArrayList<>();

    HashSet<Point> failedPoints = new HashSet<Point>();
    if(getPath(maze, maze.length -1, maze[0].length -1, path, failedPoints)) {
        return path;
    }
    return null;
}

boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path, HashSet<Point> failedPoints) {
    /* If out of bounds or not available, return. */
    if(col < 0 || row < 0 || !maze[row][col]) {
        return false;
    }

    /* If we've already visited this cell, return. */
    Point point = new Point(row, col);
    if(failedPoints.contains(point)) {
        return false;
    }

    boolean isAtOrigin = (row == 0) && (col == 0);

    /* If there's a path from the start to here, add my location. */
    if(isAtOrigin || getPath(maze, row, col -1, path, failedPoints) || getPath(maze, row-1, col, path, failedPoints)) {
        path.add(point);
        return true;

    }

    failedPoints.add(point);    // cache result
    return false;
}

Time complexity

O(r*c)

Space complexity

O(r+c), r+c is a length of the path.