Design a robot cleaner algorithm with 4 given APIs and a starting position in an unknown space (with obstacles in random locations) The 4 APIs are: clean(): clean the current location. turnleft(k): turn left k*90 degrees. turnrigt(k): turn right k*90 degrees. move(): move forward for 1 position, return False if that’s not possible. How do you clean the entire space?
Place phone call to local human cleaning service.
iRobot is hiring, huh?
1.Left-forward until false-right-forward(break if false) 2.left forward until false-left forward (break if false) Do steps 1 and 2 alternatively
I’d divert their attention to the security of this algo. What if hackers replace the call to clean with an implementation for fart ?
Indeed, this issue raises serious problems.
Breath first search on a graph. Each node needs a marker if it was cleaned or not and what it’s world frame coordinates would be. When new nodes have been created see if that node already exists if not add it to a kd tree. To deal with multiple paths to the same place I don’t think A* can help much here unless you have more information or the robot has probabilistic completion of actions
Simple DFS with recursive implementation (DFS is better than BFS in this scenario as less tiles are covered multiple times on average). Also didn't you sign an NDA for this company's interviews?
What level were you interviewing for?
Entry level big N
Wait, N as in Netflix? Since when does Netflix have entry level eng positions?
Check graph section on hackerrank
Agree with others. DFS, maintain a set of visited "nodes" to prevent going in a cycle, backtracking to ensure you navigate around obstacles
Isn’t this just exploring every node in a graph?