Find Area of Room by Robot

Posted by JH

Find Area of Room with Robot

Facebook Interview Google Interview Graph DFS

There is a robot in a room. The initial location of the robot is unknown. The shape or area of the room is unknown.
You have a remote that could walk the robot into any of the four directions - up, left, down or right. Here is the move method:

boolean move(int direction)  

direction: {0: up, 1; left, 2: right, 3: down}
If the robot hits the wall, the method returns false.
Otherwise returns true and the robot moves on to the direction given.

Find out the area of the room.

'X' marks the floor plan of the room.

A room as above has an area of 10.


This is a graph traversal problem. Either BFS or DFS could work to scan through the room.
The trick is when initial location is unknown, mark it as (0, 0) in a 2D grid.
When robot goes left: (x - 1, y)
When robot goes right: (x + 1, y)
When robot goes up: (x , y + 1)
When robot goes down: (x , y - 1)

How to store the visited locations with this setup?
There are two ways:

I. Have a class Point {int x; int y;} and a HashSet<Point>
Rewrite the equals function for Point into whenever point1.x == point2.x && point1.y == point2.y return true for point1.equals(point2).

II. Have a HashMap<Integer, HashSe<Integer>>;
        x1 : {y11, y12, y13}, 
        x2 : {y22},
        x3 : {y31, y32}

A map like above marks the visited nodes (x1, y11), (x1, y12), (x1, y13), (x2, y22), (x3, y31) and (x3, y32).

Both methods support finding a visited node in constant time.


With the robot setup in the question, it is best to go with DFS since it’s easier to move the robot around with DFS. Remember to move the robot back to the node which it comes from after each round of searching.

public class AreaOfRoom {
    Robot robot;

    //x, y is the current location of the robot
    //from is the last step taken
    //map<x, set<y>> marks the places visited
    public int getArea(int x, int y, int from, Map<Integer, Set<Integer>> room) {
        if(room.containsKey(x) && room.get(x).contains(y)) { //if this place was visited
            robot.move(moveBack(from));        //turn robot back
            return 0;              //add 0 to total area
        //mark current place visited
        if(!room.containsKey(x)) room.put(x, new HashSet<>());
        int area = 1;
        if(from != 0 && robot.move(moveBack(0))) {
            area += getArea(x, y - 1, 0, room);
        if(from != 1 && robot.move(moveBack(1))) {
            area += getArea(x + 1, y, 1, room);
        if(from != 2 && robot.move(moveBack(2))) {
            area += getArea(x, y + 1, 2, room);
        if(from != 3 && robot.move(moveBack(3))) {
            area += getArea(x - 1, y, 2, room);
        //having got the areas around the current location, walk robot back to where it was from
        return area;

    private int moveBack(int from) {
        if(from == 0) return 2;
        if(from == 1) return 3;
        if(from == 2) return 0;
        return 1;

Get one-to-one training from Google Facebook engineers

Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.
Most recent interview questions and system design topics gathered from aonecode alumnus.
One-to-one online classes. Get feedbacks from real interviewers.

Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.
New to the ground? - Develop basic coding skills with your own designated mentor.
Days before interview? - Focus on most important problems in target company question bank.

Image placeholder
One-on-One Algorithm and Coding Training
Image placeholder
One-on-One System Design Training
Image placeholder
One-on-One Mock Interview