I gave one round of interview at google last week. I'm not sure what's happening at google because they are asking crazy hard question to people.

you are given an NxM maze where each cell is either empty or a wall . There is one cell which is exit from the maze. You are tasked to find a set of universal instructions like DDRLU which applied from any position will make you exit from the maze.

After getting some hints from interviewer the solution i found below.

track current_instruction .

for each empty cell(i, j) in grid. Apply current instruction. if you reach exit then it's fine otherwise let's say you reach cell x, y.

update current_instruction = current_instruction + path from x, y to exit

you will do this for each cell./

you can prove that this work by induction.

not sure about time complexity though. seems N3M3 to me since we are iterating over each point and the length of current_instruction could be N2M2 length