## Google Interview Question for Software Engineer Interns

• 1
of 1 vote

Country: United States
Interview Type: Phone Interview

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

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.

``````#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

struct Room;

struct Door
{
Room* next_;
int keyId_;
}; // not a good representation of the real world, but convenient for the algo

struct Room
{
int keyId_ = -1;
bool hasTreasure_ = false;
vector<Door> doors_;

Room(int keyId) : keyId_(keyId), hasTreasure_(false) { }
Room(bool hasTreasure) : keyId_(-1), hasTreasure_(hasTreasure) { }
void connect(Room *next, int keyId = -1) {
doors_.push_back({ next, keyId });
next->doors_.push_back({ this, keyId });
}
};

bool hasPuzzleASolution(const Room* start)
{
unordered_map<int, vector<const Room*>> lockedRooms; // keyid -> locked rooms
unordered_set<int> keys{ { -1 } }; // collected keys
unordered_set<const Room*> explored; // rooms explored
stack<const Room*> s{ {start} }; // rooms exploreable

while (s.size() > 0) {
auto current = s.top();
s.pop();
if (explored.count(current)) continue; // multiple paths could have led me here
explored.insert(current);
if (current->hasTreasure_) return true; // found a / the one treasure
if (keys.count(current->keyId_) == 0) { // a new key
keys.insert(current->keyId_);
auto lrIt = lockedRooms.find(current->keyId_);
if (lrIt != lockedRooms.end()) { // unlocked a room
for_each(lrIt->second.begin(), lrIt->second.end(),
[&s](const Room* r) { s.push(r); });
lrIt->second.clear();
}
}
for (auto door : current->doors_) {
if (explored.count(door.next_) > 0) continue;
if (keys.count(door.keyId_) > 0) { // already have the key
s.push(door.next_);
} else {
lockedRooms[door.keyId_].push_back(door.next_);
}
}
}
return false;
}

int main()
{
Room a(false), b(1), c(3), d(-1), e(2), f(true);
a.connect(&b);
b.connect(&c, 6);
a.connect(&c, 1);
a.connect(&d, 1);
d.connect(&e, 3);
e.connect(&f, 7);
cout << hasPuzzleASolution(&a) << endl;
c.connect(&f, 2);
cout << hasPuzzleASolution(&a) << endl;
return 0;
}``````

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

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

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

cout << TreasureReachable(&r1) << "\n";
cout << TreasureReachable(&r2) << "\n";
cout << TreasureReachable(&r3) << "\n";
cout << TreasureReachable(&r4) << "\n";

return 0;
}``````

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

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;
for (RoomConnections rc : connectedRooms) {
if (!possible && ((rc.blocked && keys.contains(room.room)) || !rc.blocked) && !roc.contains(rc.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++) {
RoomConnections roomConn = null;
if (ro[j] == 2) {
int lock = roomCount;
while(lock > roomCount-1 || lock == treasureRoom){
lock = r.nextInt(MAXBOUND-MINBOUND) + MINBOUND;
}
} else if (ro[j] == 1) {
}
}
}
}
}

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

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

``````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]
if (tmp2 == 't'): res = True
elif(tmp2 != ''): objects.append(graph[start])

for next in graph[start].keys():
if next not in visited:
tmp1 = graph[start][next]
if (tmp1 in objects or tmp1 == ''):
res = find_treasure(next, graph, objects, visited, res)
return res``````

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.