I had an onsite interview round today. The interviewer was from India.

Question:

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 example 2)

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 move right through the first command (R) and exit the maze.

I was able to give a brute force solution using BFS - Apply BFS on all the valid points, store all the possible paths for all starting points and then find an interection of all paths. The interviewer wanted an optimal solution, I was not able to find it.