Google L4 Onsite Interview Round
Summary
I had an L4 onsite interview round with Google where I was presented with a complex maze navigation problem for a blind robot. I provided a brute-force BFS solution, but the interviewer sought a more optimal approach.
Full Experience
I recently completed an onsite interview round with Google for an L4 position. The interviewer I spoke with was from India. The core of the interview revolved around a challenging problem regarding a blind robot navigating a maze, which required me to devise a set of commands to ensure escape from any valid starting point.
Interview Questions (1)
Input is a maze represented by a 2D matrix. A cell can have 3 values (# - wall, . - empty cell, E - Escape point). There's a blind robot, who can travel in 4 directions (R, U, L, D). Write a set of commands such that when the robot is placed on any valid cell, it should be able to escape the maze. The robot can exit through the maze early without completing all commands as well (see examples).
Example Input 1:
#####
#...#
#..E#
#####
Output : DRR
Example Input 2:
####
#.E#
##.#
####
Output : RU
Explanation:
For the Bottom valid cell(2,3) => The robot will hit Wall first(R) and then move Upwards(U) and exit the maze.
For the First valid cell(1,2) => The robot will exit through the first command (R) and exit the maze.