Google Interview Question
Software Engineer InternsCountry: United States
Interview Type: Phone Interview
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
using namespace std;
class Room;
class Door {
public:
Door(Room *to_room, int lock)
{
to_room_ = to_room;
lock_ = lock;
}
Room *to_room_;
int lock_;
};
class Room {
public:
Room(bool treasure, int key)
{
treasure_ = treasure;
key_ = treasure ? 0 : key;
}
~Room()
{
for (auto door : doors_) {
delete door;
}
}
void AddDoor(Room *to_room, int lock)
{
bool found = false;
for (auto door : doors_) {
if (door->to_room_ == to_room) {
found = true;
break;
}
}
if (!found &&
to_room != this)
{
doors_.push_back(new Door(to_room, lock));
to_room->AddDoor(this, lock);
}
}
vector<Door *> doors_;
bool treasure_;
int key_;
};
bool TreasureReachable(Room const *start_room)
{
unordered_map<int, Room const *> lock_rooms;
unordered_set<int> keys;
unordered_set<Room const *> seen;
stack<Room const *> st;
st.push(start_room);
while (!st.empty()) {
Room const *room = st.top();
st.pop();
if (room->treasure_) {
return true;
}
if (seen.find(room) == seen.end()) {
seen.insert(room);
if (room->key_) {
keys.insert(room->key_);
if (lock_rooms[room->key_]) {
seen.erase(lock_rooms[room->key_]);
st.push(lock_rooms[room->key_]);
lock_rooms.erase(room->key_);
}
}
for (auto door : room->doors_) {
if (door->lock_) {
if (keys.find(door->lock_) != keys.end()) {
keys.erase(door->lock_);
} else {
lock_rooms[door->lock_] = room;
continue;
}
}
st.push(door->to_room_);
}
}
}
return false;
}
int main() {
/*
|----------|--------|
| r1 | r2 |
| treasure | key 1 |
| | |
|----------|--------|
| | |
| r3 | r4 |
| | key 2 |
|----------|--------|
*/
Room r1(true, 0);
Room r2(false, 1);
Room r3(false, 0);
Room r4(false, 2);
r3.AddDoor(&r1, 1);
r3.AddDoor(&r4, 0);
r4.AddDoor(&r2, 2);
cout << TreasureReachable(&r1) << "\n";
cout << TreasureReachable(&r2) << "\n";
cout << TreasureReachable(&r3) << "\n";
cout << TreasureReachable(&r4) << "\n";
return 0;
}
The idea of creating new levels, with rooms connected to other rooms, containing keys, treasure...
Needs some tuning on random generator -
public static void main(String[] args) {
Level level = new Level();
for (int i = 0; i < level.rooms.length; i++) {
System.out.println("Room - "+ level.rooms[i].room + " Treasure - "
+ level.rooms[i].treasure + " Connected to - " + level.rooms[i].connectRooms + " Contains keys - " + level.rooms[i].roomkeys);
}
boolean res = ispossible(level.rooms, 0, false, new ArrayList<Integer>(), new ArrayList<Integer>());
System.out.println(res);
}
public static boolean ispossible(Room[] rooms, int index, boolean possible, List<Integer> keys, List<Integer> roc) {
if (index < 0 || index > rooms.length - 1)
return possible;
if (rooms[index].treasure)
return true;
Room room = rooms[index];
List<RoomConnections> connectedRooms = room.connectRooms;
keys.addAll(room.roomkeys);
for (RoomConnections rc : connectedRooms) {
if (!possible && ((rc.blocked && keys.contains(room.room)) || !rc.blocked) && !roc.contains(rc.room.room)){
roc.add(room.room);
possible = ispossible(rooms, rc.room.room, possible, keys, roc);
roc.remove(new Integer(room.room));
}
}
return possible;
}
public static class Level {
static final int MINBOUND = 2;
static final int MAXBOUND = 10;
Room[] rooms = null;
public Level() {
Random r = new Random();
int roomCount = r.nextInt(MAXBOUND-MINBOUND) + MINBOUND;
int treasureRoom = roomCount;
while(treasureRoom > roomCount-1){
treasureRoom = r.nextInt(MAXBOUND-MINBOUND) + MINBOUND;
}
rooms = new Room[roomCount];
for (int i = 0; i < roomCount; i++) {
Room room = null;
if (i == treasureRoom)
room = new Room(i, true);
else
room = new Room(i, false);
rooms[i] = room;
}
int[][] ri = new int[roomCount][roomCount];
for (int i = 0; i < ri.length; i++) {
for (int j = 0; j < ri.length; j++) {
if(i == j) continue;
if (ri[i][j] == 0) {
ri[i][j] = r.nextInt(3);
ri[j][i] = ri[i][j];
}
}
}
for (int i = 0; i < ri.length; i++) {
int[] ro = ri[i];
Room room = rooms[i];
for (int j = 0; j < ro.length; j++) {
Room adjroom = rooms[j];
RoomConnections roomConn = null;
if (ro[j] == 2) {
roomConn = new RoomConnections(adjroom, true);
int lock = roomCount;
while(lock > roomCount-1 || lock == treasureRoom){
lock = r.nextInt(MAXBOUND-MINBOUND) + MINBOUND;
}
rooms[lock].roomkeys.add(j);
room.connectRooms.add(roomConn);
} else if (ro[j] == 1) {
roomConn = new RoomConnections(adjroom, false);
room.connectRooms.add(roomConn);
}
}
}
}
}
public static class Room {
int room;
boolean treasure;
List<RoomConnections> connectRooms = new ArrayList<RoomConnections>();
List<Integer> roomkeys = new ArrayList<Integer>();
public Room(int room, boolean treasure) {
this.room = room;
this.treasure = treasure;
}
@Override
public int hashCode() {
return room;
}
}
public static class RoomConnections {
Room room;
boolean blocked;
public RoomConnections(Room room, boolean blocked) {
this.room = room;
this.blocked = blocked;
}
}
graph = {
'r1': ('k1', {'r2': '', 'r3': ''}),
'r2': ('', {'r1': '', 'r3': 'k1', 'r4': 'k2'}),
'r3': ('k2', {'r1': '', 'r2': 'k1'}),
'r4': ('t', {'r2': 'k2'}),
}
def find_treasure(start, graph, objects=[], visited=None, res=False):
if visited is None:
visited = []
visited.append(start)
tmp2 = graph[start][0]
if (tmp2 == 't'): res = True
elif(tmp2 != ''): objects.append(graph[start][0])
for next in graph[start][1].keys():
if next not in visited:
tmp1 = graph[start][1][next]
if (tmp1 in objects or tmp1 == ''):
res = find_treasure(next, graph, objects, visited, res)
return res
neat!
my approach (assuming the same keyid can open a door from both sides)
Node in the graph is the room. The room has two attributes, a keyId (int) and a treasure
(bool). The edges are the doors. The door has another attribute which is the keyId (int)
it needs in order to open it. KeyId -1 is a sentinel for "no key".
To solve it, I choose a DFS which I perform until I reach a door I can't open. Then
I put the DFS branch I was exploring into a HT with key-Id as HT-key and a list of rooms
that I can continue with when I get that key id as HT-values.
It will be linear in the number of rooms if the graph is sparse, or linear in the number
of doors if the graph is dense.
- Chris October 24, 2017