Google Interview Question for Software Engineer Interns


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

- Chris October 24, 2017 | Flag Reply
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;
			}
		}
		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;
}

- Alex October 25, 2017 | Flag Reply
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;
		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;
		}
	}

- sudip.innovates November 02, 2017 | Flag Reply
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][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

- silvio.s December 15, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More