## Google Interview Question for Software Engineer / Developers

Country: United Kingdom
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
6
of 6 vote

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!

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Graph can definitely be cyclic.

Comment hidden because of low score. Click to expand.
0

@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).

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

Please explain what is not clear?

Comment hidden because of low score. Click to expand.
0

I wasn't sure if we needed to find any path or the shortest path.

Asking for A* is way too much for 40 minutes. Kind of silly.

Good luck!

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm sorry, what's wrong with using a matrix to store the floor plans?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
2

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.

Comment hidden because of low score. Click to expand.
0

In the map above,

W = Wall,
C = corridor
F = Fire Exit
L = Pull door as defined above
S = Push door as defined above

Comment hidden because of low score. Click to expand.
0

When I said "I don't think the idea is that you implement it on the fly", I meant Thorup's.

Comment hidden because of low score. Click to expand.
0

Hi some guy, I appreciate your effort for the detailed reply. I will check your solution and comment further. Thanks

Comment hidden because of low score. Click to expand.
1
of 1 vote

Here's the code, note that it's in c# :)

``````namespace FireExitsInterview
{
class Program
{
static void Main(string[] args)
{
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();
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]);
}

}

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])
{
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;
}

}
}``````

Comment hidden because of low score. Click to expand.
0

Note that if you had to only check how every door opens with respect to only one Fire Exit, you can simply call Dijkstra with that fire exit instead of going through all of them.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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);

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 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);
checkForAWay(t,visitedRoom+1,roomNbr);
}
}

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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* tail;
public:
//
};

Algo:
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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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* tail;
public:
//
};

Algo:
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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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* tail;
public:
//
};

Algo:
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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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* tail;
public:
//
};

Algo:
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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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:
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)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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:
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)

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.