The interview experience was good overall, and the interviewer was very friendly. This time I got a classic grid graph search/simulation question. The problem statement was quite long and needed careful reading. The original question follows:
Problem description:
Imagine a board of size numRows × numColumns with some lasers on it. These lasers are located in the two-dimensional array laserCoordinates, where laserCoordinates
is a two-element array containing the center coordinates of the ith laser. A laser at cell (row, column) destroys everything in the same row (the row with index row) and the same column (the column with index column).
Now imagine a robot at coordinates (curRow, curColumn). The robot can move only in a straight line within the board: left, right, up, or down. Your task is to calculate the maximum number of cells it can safely move through in any direction before being destroyed by a laser.
Note:
Assume the starting cell is protected. Even if a laser's destruction area covers that cell, the laser cannot destroy the robot there.
An optimal solution is not required, but a solution with time complexity no greater than O(numRows [i] numColumns
laserCoordinates.length) will pass within the time limit.
Example:
Input:
numRows = 8, numColumns = 8, curRow = 5, curColumn = 3, laserCoordinates = [[1, 6], [2, 8]]
Output:
3
Explanation:
On an 8x8 board, two lasers are at (1, 6) and (2, 8). According to the animation, the robot's longest safe path is 3, moving upward from its starting position.
[Sharing my approach]
Preprocess the lasers: Since lasers cover entire rows and columns, we can extract all laser row and column indices and store them in two sets, laserRows and laserCols.
Simulate all four directions: Traverse upward, downward, leftward, and rightward separately. Since the suggested time-complexity bound is O(numRows
numColumns
laserCoordinates.length), checking each cell for laser coverage by brute force might time out. The optimal approach is to use the preprocessed row and column sets. During the simulation, before each move, check whether the destination cell's row or column is in a set. If so, stop; otherwise, keep moving and counting.
Handle the starting position: According to Note 1, the starting position ignores laser threats. So the simulation starts there, and the first step is safe no matter what. Keep going until reaching a row or column covered by a laser.
Return the maximum: Take the maximum number of steps possible in the four directions.
[Difficulty assessment]
Medium difficulty. The main challenge is the long problem statement: you need to quickly identify the core constraints, especially protection of the starting position and coverage of entire rows and columns. The explicit time-complexity bound suggests that brute-force DFS/BFS checking lasers at every step is not suitable; the row and column states need to be preprocessed.
Discussion
Loading comments…