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.

e.g.
X
XXXX
XX
'X' marks the floor plan of the room.

A room as above has an area of 10.

Solution

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.

Implementation

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<>());
room.get(x).add(y);
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
robot.move(moveBack(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.

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