Google Interview Question
Software Engineer / DevelopersCountry: United Kingdom
Interview Type: In-Person
Please explain how will the resulting representational graph is acyclic. It might not be acyclic. Try an example where four rooms connected like a 2x2 having doors that pushes towards each in sequence. This will be cyclic.
Ex:
|A|B|
-- ---
|D|C|
A has pushdoor to b, b to c, c to d, d to a.
Being cyclic does not stop you from DFS or BFS
@Victor since we are checking if *all* paths are push to the fire exit (not shortest path, or even if there is exists a path, but if ALL paths go to it) then we have to conclude that we are talking about acyclic paths to the exit, else any building with two rooms would fail the test (I can walk through push door 1, then walk about through it, and thus fail).
Problem is not very clear. Still, I came up with a solution.
Construct a graph where the vertices are the rooms, corridors, and fire exits; and the edges are the doors. Naturally these edges are directed in the same way as the corresponding doors.
For the floor design to be valid, any vertex of fire exit should be reachable from every vertex of room.
Reachability in planar graphs (which is the case here) can be computed in O(VlogV) using Thorup's Algorithm. An alternative could be regular DFS or BFS, but they are more expensive.
What means that the door "opens towards the fire exit"? I think that it must to a room which is closer to the fire exit than the previous room.
So, the data structure is the list of graph nodes, where each node has list of all egdes that are incident to it (that is, doors of that room with the direction of each door).
To determine correctness of all doors' directions we can use BFS which uses rooms with fire exits as starting points. Whenever we process a door to an unvisited room, this door must towards the current room. If this rule is violated, then the design is not fire safe.
The complexity of an algorithm is O(V * E), since we visit all rooms and check all the doors once.
Imagine solving this in 40 mins and the guy expected an A* algorithm based solution. I gave a graph based solution.
But the graph has two type of nodes - A room node and exit door node. Each room is connected to other by a directed edge that connects room1 to 2 if the door pushes from 1 to 2. All we need to do is to check from each room if there is atleast one path towards one of the fire exits.
Please note that this graph might not be acyclic.
Doing a BFS starting from one room node, gives the shortest path towards from this room to all the fire exits. If there exits a path to atleast one fire exit in this graph, then it is fine. Doing BFS from all the nodes can solve the problem of verification.
another solution is do a BFS or DFS and get parents of each node in the resulting traversal tree. Then check if there is a path from each room to one of the fire exits.
Need to see how to do this using A* algorithm and a 2d array representation of the room
I'm sorry, what's wrong with using a matrix to store the floor plans?
You would need to find the shortest path to each exit, going through doors first, avoid walls, only walk through floor, then check if the doors open in the direction of that directed path or not, right?
Please explain which approach will be faster, a floor plan as matrix or graph which has the directions internally coded? How would you model the matrix and how would you design the algorithm? Can you answer in detail?
Hi Phoenix,
A few considerations to be made:
1. You are interested only in the path to the closest Fire Exit from each door
2. Doors should always open towards the closest fire exit, even if there are others.
3. Define what is pull and what is push (ie: if the door opens toward the north or the east, we are pushing, else we are pulling)
I would represent the matrix in the following way:
WWWWWWWWWWWWWWWWWW
FCCCCCCCCCCCCWCCCF
WWWWWWWWWWWWSWCCCW
WCCCCCCCCCCWCWCCCW
FCCCCCCCCCCLCWCCCW
WWWWWWWWWWWWCWCCCW
WWCCCCCCCCCCCLCCCW
WWWWWWWWWWWWWWWWWW
The simplest viable (no bruteforcing) solution would be dijsktra.
1. Choose the initial positions for each door and get the shortest distance to each Fire exit.
1.1. Consider walls as having distance infinity.
1.2. Consider each move costs "1" if it is going through a door, or reaching a fire exit.
2. Once you have each of the paths, get the "next step" for each of the doors. Ie: If the door is push, and you should move south to get to the closest fire exit, that door is not correct, and should be "pulled" instead
3. While it doesn't improve the order, you can save time by recognizing doors you have been through in different paths, and not duplicating time.
You could use Thorup's, but the implementation is somewhat more complicated for a 30-40 minute interview, and I don't think the idea is that you implement it on the fly, but rather that you can solve the problem. If you knew about it, then I suppose it would help to mention it, but you want to be able to solve the problem on the fly. This avoids having to code an entire graph, and really, it's just a map of the floor.
In the map above,
W = Wall,
C = corridor
F = Fire Exit
L = Pull door as defined above
S = Push door as defined above
When I said "I don't think the idea is that you implement it on the fly", I meant Thorup's.
Hi some guy, I appreciate your effort for the detailed reply. I will check your solution and comment further. Thanks
Here's the code, note that it's in c# :)
namespace FireExitsInterview
{
class Program
{
static void Main(string[] args)
{
string text = File.ReadAllText(@"C:\Users\Ricardo\Desktop\floor.txt");
string[] lines = text.Split(new string[]{"\r\n"}, StringSplitOptions.RemoveEmptyEntries);
List<int[]> doorPositions = new List<int[]>();
List<int[]> fireExits = new List<int[]>();
List<int[]> pendingPositionList = new List<int[]>();
//we will store both the distance and the previous node
//we'll encode the positions as i * lines.Length + j
int posCount = lines.Length * lines[0].Length;
int[][] distances = new int[posCount][];
//Assuming rectangular floors, just for the sake of simplifying
//the problem
bool[] visitedPositions = new bool[posCount];
//Record all Door positions and Fire Exits and initialize arrays
for (int i = 0; i < lines.Length; i++)
{
for(int j = 0 ; j < lines[i].Length; j++)
{
if (lines[i][j] == 'F')
fireExits.Add(new int[] { i, j });
if (lines[i][j] == 'S' || lines[i][j] == 'L' )
doorPositions.Add(new int[] { i, j });
//
distances[i * lines.Length + j] = new int[] { int.MaxValue, -1 };
visitedPositions[i * lines.Length + j] = false;
}
}
//Here we'll save the shortest distance from a door to any fire escape
//and whether or not it opens correctly
int[][] doorDistances = new int[posCount][];
//Let's apply dijkstra for each fire exit, that is, from each fire exit to each door:
//Reason being that Dijkstra allows us to easily get previous node,
//hence if the last node is the door we don't need to traverse
//anything, we just get the previous node to find out what direction it should open
for (int i = 0; i < fireExits.Count; i++)
{
RestartArrays(distances, visitedPositions);
pendingPositionList.Clear();
pendingPositionList.Add(fireExits[i]);
Dijkstra(fireExits[i][0], fireExits[i][1], lines, distances, pendingPositionList, doorDistances);
}
for (int i = 0; i < doorPositions.Count; i ++ )
{
int encPos = doorPositions[i][0] * lines.Length + doorPositions[i][1];
Console.WriteLine("Door at {0},{1} opens {2} towards Fire Exit at {3},{4}. Distance is: {5}",
doorPositions[i][0],
doorPositions[i][1],
doorDistances[encPos][1] > 0 ? "correctly" : "incorrectly",
doorDistances[encPos][2],
doorDistances[encPos][3],
doorDistances[encPos][0]);
}
Console.ReadLine();
}
private static void RestartArrays(int[][] distances, bool[] visitedPositions)
{
for (int i = 0; i < visitedPositions.Length; i++)
{
distances[i] = new int[] { int.MaxValue, -1 };
visitedPositions[i] = false;
}
}
//For simplicity let's assume only 4 possible movements
static int[][] movementMatrix = { new int[] { 1, 0 }, new int[] { -1, 0 }, new int[] { 0, -1 }, new int[] { 0, 1 } };
//We want to find all doors, so there's no final position.
//We will just go through all the reachable spots for each fire escape.
//If one corresponds to a door, we'll take it into account
static void Dijkstra(int initialX, int initialY, string[] map, int[][] distances, List<int[]> pendingPositionList, int[][] doorDistances)
{
//encoded value for position
int encPos = initialX * map.Length + initialY;
distances[encPos][0] = 0;
distances[encPos][1] = initialX * map.Length + initialY;
while (pendingPositionList.Count > 0) {
int[] currentPos = pendingPositionList[0];
encPos = currentPos[0] * map.Length + currentPos[1];
pendingPositionList.RemoveAt(0);
// we try to move in all four directions
for (int i = 0; i < movementMatrix.Length; i++)
{
int[] newPos = new int[] { currentPos[0] + movementMatrix[i][0], currentPos[1] + movementMatrix[i][1] };
if (!IsValidPosition(map, newPos))
//Not a valid position
continue ;
char newPosType = map[newPos[0]][newPos[1]];
int encNewPos = newPos[0] * map.Length + newPos[1];
int newDist = distances[encPos][0] + 1;
//if it's not a Wall or another Fire Exit.
//Note that we will keep going even if we find a door
if (IsNotWallOrFireExit(newPosType))
{
if (newDist < distances[encNewPos][0])
{
pendingPositionList.Add(newPos);
distances[encNewPos][0] = newDist;
distances[encNewPos][1] = encPos;
}
}
if (IsDoor(newPosType))
{
//We found a door. If it's the first
//time we get to this door, let's add it
if (doorDistances[encNewPos] == null)
{
//Second parameter is used to determine if it opens correctly.
doorDistances[encNewPos] = new int[] { int.MaxValue, -1, -1, -1 };
}
//Here we'll update if the distance is shorter, or if the previous route we found
//indicated that the door didn't open correctly.
if (newDist < doorDistances[encNewPos][0] || newDist == doorDistances[encNewPos][0] && doorDistances[encNewPos][1] <= 0)
{
doorDistances[encNewPos][0] = newDist;
doorDistances[encNewPos][1] = IsCorrectlyPositioned(newPosType, currentPos, newPos) ? 1 : 0;
doorDistances[encNewPos][2] = initialX;
doorDistances[encNewPos][3] = initialY;
}
}
}
}
}
private static bool IsCorrectlyPositioned(char newPosType, int[] currentPos, int[] newPos)
{
//If we'll pull currentPos should be south (door I < current I)
// or west (door J < current J).
if(newPosType == 'L')
{
return currentPos[0] > newPos[0] || currentPos[1] < newPos[1];
}
//Other way around if the door is marked as push.
if (newPosType == 'S')
{
return currentPos[0] < newPos[0] || currentPos[1] > newPos[1];
}
return false;
}
private static bool IsDoor(char newPosType)
{
return newPosType == 'L' || newPosType == 'S';
}
private static bool IsNotWallOrFireExit(char newPosType)
{
return newPosType != 'W' && newPosType != 'F';
}
private static bool IsValidPosition(string[] map, int[] newPos)
{
return newPos[0] >= 0 && newPos[1] >= 0 && newPos[0] < map.Length && newPos[1] < map[0].Length;
}
}
}
public boolean isOpenedAll(HashMap<Integer, int[]> floor){
if(floor == null) return false;
for(int[] doors : floor.values()){
if(isOpenedEach(doors)) return false;
}
return true;
}
private boolean isOpenedEach(int[] doors){
if(doors.length <= 0) return false;
for(int i : doors){
if(i==0) return false;
}
return true;
}
import java.util.ArrayList;
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//Room(roomName, hasFireExist)
Room a = new Room("A", false);
Room b = new Room("B", false);
Room c = new Room("C", false);
Room d = new Room("D", false);
Room e = new Room("E", false);
Room f = new Room("F", true);
Room g = new Room("G", true);
Room h = new Room("H", true);
//Room(doorType, roomAccess)
Door d1 = new Door("push", b);
Door d2 = new Door("push", c);
Door d3 = new Door("push", e);
Door d4 = new Door("pull", h);
Door d5 = new Door("push", d);
Door d6 = new Door("push", g);
Door d7 = new Door("push", f);
Door d8 = new Door("push", h);
a.addDoor(d1);
a.addDoor(d2);
b.addDoor(d3);
c.addDoor(d4);
e.addDoor(d5);
e.addDoor(d6);
g.addDoor(d7);
g.addDoor(d8);
checkForAWay(new TreeWay(a,""),0,8);
}
public static class Door
{
String type;
public Room room;
public Door(String type, Room room)
{
this.type = type;
this.room = room;
}
public boolean isPushed()
{
return type.equals("push");
}
}
public static class Room
{
public String name;
ArrayList<Door> doors = new ArrayList<Door>();
boolean hasFireExist;
public Room(String name, boolean fe)
{
this.name = name;
this.hasFireExist = fe;
}
public void setHasFireExist(boolean b)
{
hasFireExist = b;
}
public void addDoor(Door door)
{
doors.add(door);
}
public ArrayList<Door> getDoors()
{
return doors;
}
public boolean hasFireExist()
{
return hasFireExist;
}
}
public static class TreeWay
{
public String wayString;
public Room room;
public ArrayList<TreeWay> gotoList = new ArrayList<TreeWay>();
public TreeWay(Room room,String previousSWay)
{
this.room = room;
wayString = previousSWay+" -> "+room.name;
}
}
public static void checkForAWay(TreeWay tree,int visitedRoom,int roomNbr)
{
if(tree.room.hasFireExist())
{
System.out.println("YES "+tree.wayString);
}
boolean allAreClosed = true;
for(Door door : tree.room.getDoors())
allAreClosed = allAreClosed && (!door.isPushed()) ;
if((allAreClosed)&&(!tree.room.hasFireExist()))
{
System.out.println("BLOCKED "+tree.wayString);
}
if((visitedRoom>roomNbr)&&(!tree.room.hasFireExist()))
{
System.out.println("NO WAY "+tree.wayString);
}
for(Door door : tree.room.getDoors())
{
if(door.isPushed())
{
TreeWay t = new TreeWay(door.room,tree.wayString);
tree.gotoList.add(t);
checkForAWay(t,visitedRoom+1,roomNbr);
}
}
}
}
Data structure:
A double linked list represents floor, each node is a door, a door has next pointer to represent being pushed towards fire exit, a door has prev pointer to represent being pulled towards fire exit. A door can have either next or prev pointer but not both. A door may optionally have a son pointer which points to a sub-floor. An fire exit has both next and prev pointers.
class Door {
Door* next;
Door* prev;
Door* son;
};
class Floor {
private:
Door* head;
Door* tail;
public:
//
};
Algo:
start from head:
if a node with next only is found, move to its next node (push door, so we expect we meet all push doors until meet a fire exit)
if a node with prev only is found, a wrong pull door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list
start from tail:
if a node with prev only is found, move to its prev node (note: pull door from head direction definition is actually "push" door from tail direction, so we expect we meet all pull doors until meet a fire exit)
if a node with next only is found, a wrong push door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list
note: if start from any Door node:
depend on if it is a push or pull door, execute either of the two loops above (i.e. check all doors on the route towards fire exit has same push/pull attribute)
Only after all are checked and pass, return success (1)
Data structure:
A double linked list represents floor, each node is a door, a door has next pointer to represent being pushed towards fire exit, a door has prev pointer to represent being pulled towards fire exit. A door can have either next or prev pointer but not both. A door may optionally have a son pointer which points to a sub-floor. An fire exit has both next and prev pointers.
class Door {
Door* next;
Door* prev;
Door* son;
};
class Floor {
private:
Door* head;
Door* tail;
public:
//
};
Algo:
start from head:
if a node with next only is found, move to its next node (push door, so we expect we meet all push doors until meet a fire exit)
if a node with prev only is found, a wrong pull door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list
start from tail:
if a node with prev only is found, move to its prev node (note: pull door from head direction definition is actually "push" door from tail direction, so we expect we meet all pull doors until meet a fire exit)
if a node with next only is found, a wrong push door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list
note: if start from any Door node:
depend on if it is a push or pull door, execute either of the two loops above (i.e. check all doors on the route towards fire exit has same push/pull attribute)
Only after all are checked and pass, return success (1)
Data structure:
A double linked list represents floor, each node is a door, a door has next pointer to represent being pushed towards fire exit, a door has prev pointer to represent being pulled towards fire exit. A door can have either next or prev pointer but not both. A door may optionally have a son pointer which points to a sub-floor. An fire exit has both next and prev pointers.
class Door {
Door* next;
Door* prev;
Door* son;
};
class Floor {
private:
Door* head;
Door* tail;
public:
//
};
Algo:
start from head:
if a node with next only is found, move to its next node (push door, so we expect we meet all push doors until meet a fire exit)
if a node with prev only is found, a wrong pull door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list
start from tail:
if a node with prev only is found, move to its prev node (note: pull door from head direction definition is actually "push" door from tail direction, so we expect we meet all pull doors until meet a fire exit)
if a node with next only is found, a wrong push door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list
note: if start from any Door node:
depend on if it is a push or pull door, execute either of the two loops above (i.e. check all doors on the route towards fire exit has same push/pull attribute)
Only after all are checked and pass, return success (1)
Data structure:
A double linked list represents floor, each node is a door, a door has next pointer to represent being pushed towards fire exit, a door has prev pointer to represent being pulled towards fire exit. A door can have either next or prev pointer but not both. A door may optionally have a son pointer which points to a sub-floor. An fire exit has both next and prev pointers.
class Door {
Door* next;
Door* prev;
Door* son;
};
class Floor {
private:
Door* head;
Door* tail;
public:
//
};
Algo:
start from head:
if a node with next only is found, move to its next node (push door, so we expect we meet all push doors until meet a fire exit)
if a node with prev only is found, a wrong pull door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list
start from tail:
if a node with prev only is found, move to its prev node (note: pull door from head direction definition is actually "push" door from tail direction, so we expect we meet all pull doors until meet a fire exit)
if a node with next only is found, a wrong push door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list
note: if start from any Door node:
depend on if it is a push or pull door, execute either of the two loops above (i.e. check all doors on the route towards fire exit has same push/pull attribute)
Only after all are checked and pass, return success (1)
Data structure:
A double linked list represents floor, each node is a door, a door has next pointer to represent being pushed towards fire exit, a door has prev pointer to represent being pulled towards fire exit. A door can have either next or prev pointer but not both. A door may optionally have a son pointer which points to a sub-floor. An fire exit has both next and prev pointers.
Algo:
start from head:
if a node with next only is found, move to its next node (push door, so we expect we meet all push doors until meet a fire exit)
if a node with prev only is found, a wrong pull door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list
start from tail:
if a node with prev only is found, move to its prev node (note: pull door from head direction definition is actually "push" door from tail direction, so we expect we meet all pull doors until meet a fire exit)
if a node with next only is found, a wrong push door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list
note: if start from any Door node:
depend on if it is a push or pull door, execute either of the two loops above (i.e. check all doors on the route towards fire exit has same push/pull attribute)
Only after all are checked and pass, return success (1)
Data structure:
A double linked list represents floor, each node is a door, a door has next pointer to represent being pushed towards fire exit, a door has prev pointer to represent being pulled towards fire exit. A door can have either next or prev pointer but not both. A door may optionally have a son pointer which points to a sub-floor. An fire exit has both next and prev pointers.
Algo:
start from head:
if a node with next only is found, move to its next node (push door, so we expect we meet all push doors until meet a fire exit)
if a node with prev only is found, a wrong pull door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list
start from tail:
if a node with prev only is found, move to its prev node (note: pull door from head direction definition is actually "push" door from tail direction, so we expect we meet all pull doors until meet a fire exit)
if a node with next only is found, a wrong push door is found before fire exit, return failure (0)
if next node has both next and prev, a fire exit is found, stop
if a node has son pointer, recursively checkt the sub-list
note: if start from any Door node:
depend on if it is a push or pull door, execute either of the two loops above (i.e. check all doors on the route towards fire exit has same push/pull attribute)
Only after all are checked and pass, return success (1)
I think a DAG will do it. Also, to check reverse all the edge-directions and do DFS/BFS from fire-exit. If you're able to reach all of the doors from fire-exit. Bingo!
- NaturalNikhil November 23, 2014