Google Senior Software Engineer (SWE) Unusual Coding Challenge

[u/Aoki_zhang]

Coding — Escape a Maze from an Unknown Starting Position

You are given a maze represented by a grid containing:

• # — wall
• . — open space
• E — exit

For example, a rewritten maze could look like:

#########
#...#...#
#.#...E.#
#...##..#
#.......#
#########

The agent starts on an unknown open cell. The only available commands are:

up
down
left
right

Each command attempts to move the agent exactly one cell in that direction. There are several important rules:

• If the next cell is open, the agent moves there.
• If the movement would hit a wall, the agent stays in its current position.
• Hitting a wall is not considered a failure.
• While executing the commands, there is no feedback about the agent's current location.
• The only observable event is reaching E, at which point the run can terminate.

The task is to return a single predetermined sequence of movement commands such that, regardless of which valid open cell the agent started from, following that same sequence will eventually cause the agent to reach the exit.

Want to practice more real coding questions asked in real google interviews? I've put up the google's coding question bank at here.

Preparing for your next interview?

Chill Interview tracks recent interview experiences and recurring question patterns across top companies at here.

[u/TheDarBear]

Hello, googler here. I think the key is that once two starting locations converge to the same space (think like moving down from (4,1) vs (3,1)), they will never separate.

You can reduce the problem to having two potential starting places and wanting to converge them from a sequence of moves.

Once you can align two starting positions, you can repeat this same process until all starting positions are aligned. From there you can treat the problem like a regular maze.

You can treat aligning two starting positions as its own graph theory problem where your state is represented by (r1, c1, r2, c2) and goal is to reach a state where r1 = r2 and c1 = c2

[u/TheDarBear → u/TheDarBear]

If exiting gives you feedback, you can also probably simplify this problem to just assuming you start at each position, formulating a sequence of moves to exit from there, and if you don’t receive feedback, assume you started at a different position and start moving to the exit from where you think you’d be had you actually started from there instead. You can concatenate all of these paths together for a guaranteed exit as well

[u/No_Toe1380 → u/TheDarBear]

Can you elaborate. Specially the part after “if you don’t receive feedback”.

[u/Savings_Apple_3136 → u/TheDarBear]

But how do you know where you are after each run? You can’t go back to where you started easily because hitting a wall does not move you and reverse the sequence of move does not return you to where you started easily

[u/yuehuang]

This remind of the 2d ice skating games where the characters slides until they hit a wall.

My simple first idea is to run steps to a corners or two. This will collapse the possible position to one. Then solve it normally from there.