Amazon Online Assessment (OA) - Move The Obstacle
You are in charge of preparing a recently purchased lot for the Company's building.
The lot is covered with trenches and has a single obstacle that needs to be taken down before the foundation is prepared for the building.
The demolition robot must remove the obstacle before the progress can be made on the building.
- The lot is flat, except the trenches, and can be represented by a 2D grid.
- The demolition robot must start at the top left corner of the lot, which is always flat, and can move on the block up, down, right, left
- The demolition robot cannot enter trenches and cannot leave the lot.
- The flat areas are indicated by
1, areas with trenches are indicated by
0, and the obstacle is indicated by
The input consists of three arguments:
integer represents the number of rows
integer represents the number of columns
2d grid of integers
integer that indicated the minimum distance traversed to remove the obstacle else return
numColumns <= 1000
numRows = 3 numColumns = 3 lot = [ [1, 0, 0], [1, 0, 9], [1, 9, 1]
Starting from the top-left corner, the demolition robot traversed the cells
(0,0) -> (1,0)-> (2,0)->(2,1)
The robot moves
3 times to remove the obstacle
Try it yourself
- preview_end: ""
#!/usr/bin/env python3 from collections import deque from typing import List def move_the_obstable(lot: List[List[int]]) -> int: ''' >>> move_the_obstable([ ... [1, 0, 0], ... [1, 0, 0], ... [1, 9, 1], ... ]) 3 ''' num_rows = len(lot) num_cols = len(lot) def get_neighbors(coord): row, col = coord for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]: r = row + dx c = col + dy if 0 <= r < num_rows and 0 <= c < num_cols: yield (r, c) def bfs(start): queue = deque([start]) r, c = start lot[r][c] = 0 dist = 0 while len(queue) > 0: dist += 1 n = len(queue) for _ in range(n): node = queue.popleft() for r, c in get_neighbors(node): if lot[r][c] == 9: return dist if lot[r][c] == 0: continue queue.append((r, c)) lot[r][c] = 0 return bfs((0, 0)) if __name__ == '__main__': import doctest doctest.testmod()