I recently found myself in a technical phone interview (2nd stage) and blanked when I got presented the question.

Here is the question I got asked:

Given a 2D grid cells with walls. You can move up, down, left, right. These are walks.
There is a box in the cells. The box can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. This is a push.
There is a target cell. You need to move the box to target cell.
Calculate the plan to move which minimizes the number of pushes.

Like:

###########
#T## . . . . . .#
# .# .# . .####
# . . . . B      .#
#. #####    .#
# .  .  .  .  S  .#
###########:

r = row;
c = column;
S: start point
B: box
. : empty cell
#: wall
T: target

I was able to make basic observations and sketch those in code:

• use breath first search to find the shortest path of box to target
• box can only be pushed if person can reach a cell next to the box that is aligned with the direction it wants to push to (push right, person has to be left of box, ..)
• box can only be pushed if there is no wall next to the box in the direction we want to push

My intuition:
Collect a number of "shortest paths" of the box to target and filter the feasbile ones with respect to if the person can make the pushes for this path, i.e. can access all cells it needs to access to make the pushes for each path.

My brute force:
Calculate the path from the current cell to the cell where I am going to push from next. The algorithm becomes complex in time, the interviewer wanted me to find something more efficient.

Optimization (attempt):
I sketched a thought about finding cycles within the maze, this way the man can always reach a cell within that cycle independently of the location of the box and we don't have to recalculate if man can reach cell each BFS iteration.

Confusion:
Is this about mimizing the box path or the minizing the person's walk? The interviewer said both matters. I could not clarify further.

The interviewer gave a hint: "focus on the person instead of the box".

I have been practicing (training really) for my technical interviews throughout the last 3-4 months, I did ~250 leet code questions (72 easy, 132 medium, 51 hard). What can I do to
a) not blank (blank less)
b) to handle the situation when I don't know an answer better

What am I missing to pass this specific interview and what can I do about it?

UPDATE:
The interviewer explained a solution at the end of the interview which included something along the lines of storing the position of the box along with the person position on each BFS iteration and he also said something about a priority-queue but I unfortunately could not follow him.

In hindsight, I feel this interview suffered from poor communication between the two of us:

• From the beginning I was not able to clarify what is the target of the question "Calculate the plan to move which minimizes the number of pushes.". What exactly is a plan?
• The interviewer seemed to cut me off when I tried to explain and elaborate on a brute force solution (BFS with checks if the person can reach required cells)
• The hint from the interviewer "focus on the person" did not trigger any new observations in me

And the interview hit a blind spot of mine:

• Dijkstra's algorithm. I haven't found many algorithms on leetcode that required Dijkstra so I did not study it since I have been out of school. I will quickly close that gap and also look into A* search.

In retrospective I wish I would have given a detailed analysis of all the things I know and all the problems that I see and get really detailed on it. Pushing through on talking about the brute force solution and all possible optimizations in detail would have helped with that.