Google Prep

Question 1

You are given an m x n integer matrix grid where each cell is either 0 (empty) or 1 (obstacle). You can move up, down, left, or right from and to an empty cell in one step.

Return the minimum number of steps to walk from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1) given that you can eliminate at most k obstacles. If it is not possible to find such walk return -1.

Answer 1

Utilize breadth first search with a visited array having an extra index noting the number of obstacles eliminated to factor in the visited tiles.
Usual BFS characteristics e.g. check visited and then set visited before adding to queue.
Return -1 at the end if it’s not possible to reach there altogether (no solution guaranteed).

Remember to allocate k+1 spaces in the array
TC: O(m * n * k) SC: O(m * n * k)

Question 2

Your car starts at position 0 and speed +1 on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions ‘A’ (accelerate) and ‘R’ (reverse):

When you get an instruction ‘A’, your car does the following:
position += speed
speed *= 2
When you get an instruction ‘R’, your car does the following:
If your speed is positive then speed = -1
otherwise speed = 1
Your position stays the same.
For example, after commands “AAR”, your car goes to positions 0 –> 1 –> 3 –> 3, and your speed goes to 1 –> 2 –> 4 –> -1.

Given a target position target, return the length of the shortest sequence of instructions to get there.

Answer 2

Utilize breadth first search, with state being either an extra A or an extra R direction (with final case being if the car reaches the target distance). Meanwhile, only add a if Math.abs(newPos - target) < target, and only add R if Math.abs(currPos - target) < target.

Utilize a visited pair set as per most breadth first search questions and add new pair as visited to visited array when adding to new state.