Google Interview Question
SDE1sCountry: United States
I think an easier approach would be to do a simple DFS, so that when you “backtrack” you just command the robot to move back to the parent field. You explore the room structure on the fly. This would not be optimal, since you probably visit a field a number of times, but can be easily implemented under 30 minutes. Also, correctness is easy to see.
I figured a good approach is a maze runner that detects the outer contour of the rooms. Then it should zig-zag through the interiour, similar like flood filling. It's going to be hard to prove it will really work in 30 minutes - as it is to implement it correct in 30 minutes.
- Chris December 03, 2017