Google Onsite. L5, Need help

Round 1

Questions: You have two 2D matrices which represent a grid world. Let's assume they are of size NxN. One matrix is called obstacles and is a boolean matrix where true means an obstacle you can't go in. The second matrix is an energy matrix which represents integers in the range of -5 to 5. You have a robot which is located somewhere on this map and has some starting_energy and the robot has a maximum capacity of 100 energy (if you had 98 energy and collected 8, you will still get 100).

Each turn your robot can move in 4 cardinal directions (up, down, left, right) or can stay where it is. Each move costs him move_cost energy (if you have less than that, you can't move) and it costs you nothing to stay where you are. You can move according to your obstacles matrix. Now when you are at the end of each turn you will get energy from the tile you are located at (if it is positive you will gain this energy, negative will lose it). You have no restrictions on how many times you stay at some tile, can return to the tile as many times as possible. Also, it is acceptable if you reach the final position and then your energy is fully depleted (for example, you reach the final position with 3 energy, and that position is -5 energy so you become fully out of energy).

Your goal is to find a way to reach some location with as few turns as possible and return the path. If you can't do this (either it is blocked or you ran out of energy) return an empty path. If there are multiple ways to reach it in some minimum number of turns, you should reach it with maximum possible energy.

For example, let's assume that our matrix of obstacles is empty and our energy is:

[5, -1, -3, -2]
[-3, 1, -5, -2]

You start at position (0, 1) (at that -1) and need to reach (1, 3). You start with 1 energy and it costs you 1 energy to move. Your best path is:

• move to (0, 0). Your energy will be 1 - 1 + 5 = 5
• stay at (0, 0). Your energy will be 5 + 5 = 10
• move to (0, 1). Your energy will be 10 - 1 - 1 = 8
• move to (0, 2). Your energy will be 8 - 1 - 3 = 4
• move to (0, 3). Your energy will be 4 - 1 - 2 = 1
• move to (1, 4). Your energy will be 1 - 1 - 2 = -2. As you see you were able to reach the final position and then your energy became negative.

But for example, if you start with (0, 2), it is impossible to reach (1, 3).

I tried to solve this with a priority queue (steps, negative_energy, y, x) (I was using Python and negative energy to ensure we prioritize it) and maintained a visited_set of (y, x, energy) tuples. To be able to recover the path I was storing pointers to the previous location. Interviewer told that my general approach is correct, but I failed a few of his tests. I tried to find the issue with the code but was not able to. Seems like he also tried, as after some time he told that this is not important and asked a few follow-ups.

Follow-up Questions:

• What if you want to do the same, but need to reach the destination with at least x energy?
• Can you speed up the algorithm with some heuristics?