Implement an algorithm for a room cleaning robot

Question

I wanted to ask this question to my interview candidates, hence wanted to first give it a shot to see if this is doable in 45 mins. Here's the code that I was able to come up with in 45 minutes. Can folks please let me know if there are any logic flaws in this code?

Constraints:

1. The robot does not have any data of the room to start with.
2. The robot has to traverse the entire area of the room.
3. The room can have obstacles.
4. The robot can go front or right or left.

public interface IRobot
{
    public void TurnLeft();
    public void TurnRight();
    public bool Advance(); // This returns true if the robot is able to advance/no obstacle in that step
    public void Clean();
}

public class Node
{
    public bool Visited { get; set; }
    public bool Cleaned { get; set; }
    public Node Front { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }
}

public class RobotManager
{
    private IRobot _robot;
    private Node _rootNode;
    private Node _currentNode;
    
    public RobotManager(IRobot robot)
    {
        Validator.ThrowArgumentNullIfApplicable(robot);
        this._robot = robot;
        this._rootNode = new Node();
    }
    
    public void Clean()
    {
        Clean(_rootNode);
    }
    
    private void Clean(Node currentNode)
    {       
        if(currentNode.Cleaned)
        {
            return;
        }
        
        this._robot.Clean();
        currentNode.Cleaned = true;
        this._currentNode = currentNode;
        
        if(this._robot.Advance())
        {
            currentNode.Front = new Node();
            Clean(currentNode.Front);
        }
        
        this._robot.TurnLeft();
        if(this._robot.Advance())
        {
            currentNode.Left = new Node();
            Clean(currentNode.Left);
            this._robot.TurnRight();
        }
        
        this._robot.TurnRight();
        if(this._robot.Advance())
        {
            currentNode.Right = new Node();
            Clean(currentNode.Right);
            this._robot.TurnLeft();
        }   

        Console.WriteLine("Finished Cleaning!");
        Reset();
    }

    // This will return the robot back to the starting point
    public void Reset()
    {       
        Traverse(this._currentNode);
        this._rootNode = new Node();
    }
    
    private bool Traverse(Node currentNode)
    {
        if(currentNode == null || currentNode.Visited)
        {
            return false;
        }
        
        currentNode.Visited = true;
        if(currentNode == _rootNode)
        {
            return true;
        }
        
        if(currentNode.Front != null)
        {
            this._robot.Advance();
            if(Traverse(currentNode.Front))
            {
                return true;
            }
        }
        
        if(currentNode.Left != null)
        {
            this._robot.TurnLeft();
            this._robot.Advance();
            if(Traverse(currentNode.Left))
            {
                return true;
            }
            
            this._robot.TurnRight();
        }
        
        if(currentNode.Right != null)
        {
            this._robot.TurnRight();
            this._robot.Advance();
            if(Traverse(currentNode.Right))
            {
                return true;
            }
            
            this._robot.TurnLeft();
        }   
    }
}   
```

Answer 1

TL;DR - I would not hire you

I am going to be fair here and state that I am judging this code more harshly because you are a not just any junior developer or applicant, but you are actually responsible for testing and technically evaluating potential hires. This implies a certain skill level, and it means that you should be innately able to display what the bar for the quality of the company's code is.

And to be quite frank, as an applicant, if I saw this as the proposed solution, I would genuinely back out of working for this company.

I spent more time reviewing this than you did writing it (if you kept to your own 45 minute limit), so I hope you appreciate that I'm not trying to be mean, but I am trying to be very direct about the many issues I've uncovered. The more I looked at your code, the more started realizing that it is deeply flawed, suffers from multiple reality 101 failures, and most of all it is painfully apparent that you never even tested it, not even once.

I wouldn't hire you (for any position above junior) for several reasons:

• You are asking applicants to solve pathfinding, a notoriously difficult problem that has existed for decades and that to this day still has not been optimized (with reasonable performance), and you're giving them 45 minutes to do so. This is sheer insanity. Unless you are hiring for a game developer (or roomba developer) with significant prior experience, the posed challenge just doesn't fit the kind of applicant you're looking for.
• Some of the issues I found are related to not grasping the elemental basics of the field you're trying to work with. That's general grounds for rejecting any applicant, let alone the interviewer who created the challenge to begin with. Interviewers who don't understand the subject matter they're interviewing about are not good interviewers.
• You never even bothered to test your code. Some of these issues are blindingly obvious from the most barebones example, without even factoring in features like obstacles.
• There is not a single situation in which your code works. It's not that you've forgotten to account for fringe cases, or specific features such as obstacle avoidance. Your code fails for a 2x2 empty room.
• Furthermore, you also therefore didn't consider that applicants would like to be able to test and debug their code, which in my opinion raises red flags for both your roles as an interviewer and as a developer.

That being said, the code was formatted nicely.

I don't want to make you feel bad. We've all struggled with certain problems at one time or another. There are plenty of projects I've started that have been deeply flawed.

But I would strongly suggest you re-evaluate if you are the right person to evaluate these applicants for technical interviews. In the interest of the company, I do not think that you are the right person for the job without some significant improvements being made.

Test data and visualization tool

This is more a comment on the question rather than the solution, but behavioral logic of this kind is notorious for needing shotgun debugging. It's exceedingly hard if not impossible to see if this algorithm works as intended based on reading the code and not seeing it in action.

This applies to me needing to review your code now, you needing to check your applicants' code, as well as any applicant who'd like to debug their code while developing to find any obvious flaws.

I would strongly advise you to create a default test fixture where you have some predefined room setups to test the robot with, and a visual tool that shows you the room and the robot's progress step by step.

I will try to review your algorithm to some degree, but keep in mind that I did not write an entire test scenario for this. This is just based on what I can interpret by reading the code, and some experience I have with pathfinding logic.

Code structure

Based on the question as presented, I find it counterintuitive that you only add a robot interface without implementation, and then develop the "algorithm for a robot" in another class altogether. I'm not against separating the movement logic from the cleaning logic, but the names leave something to be desired. IRobot (and the presumed Robot class) don't indicate movement, and RobotManager doesn't indicate cleaning.

Especially for an interview question, I find this a really important sticking point. It shows you how well this developer is independently going to be able to keep your code clean.

Stack overflow

Your code relies on recursion, and the recursive stack size is finite. Therefore, you've implemented a natural cap on how big a room can be, and the way it behaves when it reaches that cap (StackOverflowException) is ugly.

I would strongly advice using some kind of iteration instead of recursion here. A for(each) is not going to be appropriate since you don't know the size of the room in advance, but a while would be appropriate here.

DRY and method naming

I don't like the Clean method name, because it is also the method which handles traversal, even though you also have a separate Traverse method. Something has gone awry here. You've duplicated the movement logic in both methods, and implemented them slightly differently.

That's not promoting reusability the way it should.

Your algorithm in general

There are frankly a lot of glaring issues with the logic itself. I can't delve into all of them in full depth. If you had had a visualization tool and test data, some of these would've been easy to spot. I'll elaborate on a few core issues, but quite frankly there's little logic to salvage here when you've noticed all the bugs.

It's important to observe that your Clean method is the only method being called to handle both the cleaning and the room traversal. Traverse is only used after the cleaning has been completed.

private void Clean(Node currentNode)
{       
    if(currentNode.Cleaned)
    {
        return;
    }

If you back out of every cleaning operation when the current node has already been cleaned, that means that you are not allowing the robot to cross a cleaned node. That is a significant flaw in your logic. The easiest test case is having a room whose obstacles are laid out like a Bomberman level:

Try traversing all the green tiles in a continuous line without crossing your path.

You might be able to snake around the level and then get into the first dead-end street, and your robot will never turn itself around (it only attempts straight, left and right).

But even if it did turn around, when it tries to exit that dead-end street, it has to drive over a path it already drove over. And what does you code do then? Refuse to continue. It tries to backtrack back into the dead-end street.

Since it is no longer adjacent to any uncleaned and accessible tile, and therefore it will report that the cleaning has been completed.

You might think that my example is a fringe case for a room that's designed to trip up your system. But your logic fails for a completely empty room as well. Your logic is as follows:

• Go straight
• If you can't, go left
• If you can't, go right
• In any of the above cases, repeat the logic
• In none of the above cases, back out and continue that recursion level's logic.

Placing the robot in a room, it's going to go straight until it can't, turn left once, go straight until it can't again, etc,... Think about what that means in visual terms:

Edit: I just noticed I forgot to number the first straight. Oops! Let's just say I totally intended to zero-index them...

After the straight that is (incorrectly) labeled 6 in the image, since it will never cross a tile that has already been cleaned, your robot has boxed itself in and will never clean the left half of the room (except the outer edge which it cleaned in the beginning).

Node-based traversal

This system just doesn't make any sense. The robot's interface is fine. You are clearly understanding that the robot only knows its own orientation, and therefore must be issued commands relative to its own position (without knowing its location in the room).

But then your node-based system throws all of that out the window and tries to dynamically build a room-scale grid, and issues commands based on the grid (which has the room as a reference point) to the robot (which has itself as a reference point).

You never check the robot's orientation. That's a massive red flag. It makes no sense to actively need to rotate a robot, and then never bother with using that rotation in your logic. Your logic decides to "go left", but since it doesn't know the orientation of the robot, how can it even figure out what "left" means to the robot?

I can't elaborate on the full ramification of this, but it essentially means that you cannot just assume that "node left" == "robot left", since the robot's orientation alters how the robot is oriented in the room. You've mixed two completely different coordinate systems and have not made sure they are compatible with one another.

Node-based traversal 2 - the big one

In my opinion, this is the biggest issue in your algorithm. This is something you should have spotted without even running the code.

Every movement moves onto a new Node(). You are not tracking any meaningful node state.

Let's imagine a 4 tile room, and the robot starts in the bottom right corner.

For brevity, I'm only focusing on the successful movement actions. The first 4 steps are what you intended them to be:

1. Go straight (new location: top-right)
2. Go left (new location: top-left)
3. Go left (new location: bottom-left)
4. Go left (new location: bottom-right)

I want to focus on what happens in step 3 when you realize that moving to the left was possible:

this._robot.TurnLeft();
if(this._robot.Advance())
{
    currentNode.Left = new Node();
    Clean(currentNode.Left);

The next node is a new Node(). But you actually already knew this location (because you have been there before). But your code makes no effort to check if this is a known location. It always blindly makes a new node.

Therefore, your entire clean-node-tracking logic is defeated:

    if(currentNode.Cleaned)
    {
        return;
    }

Since currentNode is always a newly created node, which by definition could not have been cleaned yet.

You've fallen into the age-old trap of thinking that compilers read intent, speak English, and figure out your system for you. Putting it another way:

var topLeft = new Node();
var topRight = new Node();

topLeft.Right = topRight;

var whatIsThisValue = topRight.Left;

Tell me what will be in whatIsThisValue. Is it your topRight object?

Nope. It's null. Just because left is the opposite of right doesn't mean that your code will automatically understand that "if B is right of A, then A must be left of B". That's just not how it works.

This issue renders your entire floor node state tracking logic, which the entire cleaning logic hinges on to know both how to avoid double work and to figure out when it's done, completely defeated.

Recursive backtracking

Next, we get to the recursive logic. It just doesn't make much sense. You lay out your pathfinding in recursive steps. Each recursive level will at some point attempt going forward, left and right. It doesn't just attempt one of these, it attempts all of them sequentially. When a movement attempt succeeds, it first drills down further, but the remaining movement attempts are still "queued" to happen when the recursive stack starts bubbling up again.

Following the above example, the robot will go straight for a few steps. Each step, that's a new recursive level. But you mustn't forget about the "queued" left/right commands from the first few steps. For now, you've drilled down into a new level, but what drills down will eventually bubble back up. Numbering the levels of recursion, you're looking at something like:

• Straight 1 - success
  • Straight 2 - success
    • Straight 3 - success
      • Straight 4 <---- we are currently here
    • Left 3
    • Right 3
  • Left 2
  • Right 2
• Left 1
• Right 1

No matter how deep we dig into the recursive tree, Left/Right 1/2/3 will eventually be executed when we're done digging.

The problem with this is that backtracking on the recursive stack does not backtrack the robot's actual location. Therefore, the location in which Left 1 will be executed will be completely different depending on whether or not Straight 1 succeeded or not. This makes it impossible to know which location Left 1 is actually going to visit.

When you realize the chaos that this entails, you start understanding that you don't have an algorithm here, you have a brute force attack with just loads and loads of uncoordinated random movement.

If your robot had backtracked (i.e. moved backwards) whenever your Clean method returned (and bubbled up one recursive level), your logic would have been more correct. Still bugged, but the recursive approach would've at least made more sense.

The kind of recursive logic you're using here only works when each recursive level works in its own fixed location. But because you are dealing with a real robot in a room, whose location is altered by all of those recursive levels, it becomes impossible for each recursive level to ensure that its sequential operations (straight/left/right) are executed on the same fixed location regardless of what happened on lower recursive levels.