Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
Does this problem give us a starting point?
*
. The problem guarantee that there is only one *
.What is the worst case scenario?
O(mn)
where m, n is the row and column size of grid.When we find the food, what do we return?
HAPPY CASE
Input: grid = [["X","X","X","X","X","X"],["X","*","O","O","O","X"],["X","O","O","#","O","X"],["X","X","X","X","X","X"]]
Output: 3
Input: grid = [["X","X","X","X","X"],["X","*","X","O","X"],["X","O","X","#","X"],["X","X","X","X","X"]]
Output: -1
Input: grid = [["X","X","X","X","X","X","X","X"],["X","*","O","X","O","#","O","X"],["X","O","O","X","O","O","X","X"],["X","O","O","O","O","#","O","X"],["X","X","X","X","X","X","X","X"]]
Output: 6
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For graph problems, some things we want to consider are:
X
, so that during BFS when we see a cell with X
, it is either obstacle or is already visited, so we can skip it.Plan the solution with appropriate visualizations and pseudocode.
General Idea: Find the shortest path from one point to the other.
(i, j, cnt)
, explore 4 neighbors and incrementÂ cnt
Â by 1X
Â to avoid revisit#
Â is met, returnÂ cnt
âš ď¸Ź Common Mistakes
grid[cur[0]][cur[1]] = 'X';
line, you need to do a check for if(grid[cur[0]][cur[1]] == 'X')
and then break; if that is the case.Implement the code to solve the algorithm.
class Solution {
public int getFood(char[][] grid) {
// create a queue
Queue<int[]> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == '*') {
queue.offer(new int[]{i, j});
visited.add(i + "," + j);
break;
}
}
}
int[] dx = new int[]{1, 0, 0, -1};
int[] dy = new int[]{0, 1, -1, 0};
int steps = 0;
// apply bfs
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] node = queue.poll();
if (grid[node[0]][node[1]] == '#') {
return steps;
}
for (int j = 0; j < 4; j++) {
int newx = node[0] + dx[j];
int newy = node[1] + dy[j];
if (newx >= 0 && newx < grid.length && newy >= 0 && newy < grid[0].length && grid[newx][newy] != 'X' && !visited.contains(newx + "," + newy)) {
queue.offer(new int[]{newx, newy});
visited.add(newx + "," + newy);
}
}
}
steps++;
}
return -1;
}
}
class Solution:
def getFood(self, grid: List[List[str]]) -> int:
k = l = 0
# initialize the truth table
visited = [[False]*len(grid[0]) for p in range(len(grid))]
# search for the starting position
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '*':
k,l = i,j
break
# update the starting position's value in visited
visited[k][l] = True
# initialize queue with starting position and steps calculated
queue = [(k,l, 0)]
# start the BFS process from the starting position
while queue != []:
x,y,s = queue.pop(0)
# runs in all directions
for l,r in [(-1,0), (0,1), (1,0), (0,-1)]:
# checks for edge case
if ((0 <= x+l < len(grid)) and (0 <= y+r < len(grid[0])) and not visited[x+l][y+r]):
# found food, return the number of steps
if grid[x+l][y+r] == '#':
return s+1
# found empty space, add the queue and update visited
if grid[x+l][y+r] == 'O':
queue.append((x+l, y+r, s+1))
visited[x+l][y+r] = True
# could not find any food, exit the function
return -1
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Time Complexity: O(NM)
, where M is the number of rows and N is the number of columns. We had to traverse the whole grid.
Space Complexity: O(NM)
, where M is the number of rows and N is the number of columns. We needed a visited array to keep track of the visited cells in the grid.