Google Interview Question for SDE-2s


Country: United States
Interview Type: Phone Interview




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

This is a percolation problem solvable using union-find.

The thief cannot go from left to right iff there exists a path from top to bottom via sensor coverage areas. You have a graph where two sensors are connected if their coverage areas overlap. You need to find if there exists a sensor overlapping the top side of the room that is connected with a sensor overlapping the bottom side of the room.

- adr September 15, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

OK here's some code. It can be further optimised to not use naive union-find and to not brute-force when searching for overlapping areas. Hope it helps.

# Assume all sensors are within a room, the actual width of the room does not matter.
def canGoFromLeftToRight(roomHeight, sensors, r):
    ids = range(len(sensors))

    def union(i,j):
        ids[find(i)] = find(j)

    def find(i):
        while (i != ids[i]):
            ids[i] = ids[ids[i]]
            i = ids[i]
        return i

    top = []
    bottom = []
    for i,[x,y] in enumerate(sensors):
        if y+r >= roomHeight: # overlaps top side of the room
            top += [i]
        if y <= r: # overlaps bottom side of the room
            bottom += [i]

    if not top or not bottom:
        return True

    # unite all sensors overlapping the top
    for i,j in zip(top, top[1:]):
        union(j,i)

    # unite all sensors overlapping the bottom
    for i,j in zip(bottom, bottom[1:]):
        union(i,j)

    # unite all sensors overlapping each other
    for i,[x,y] in enumerate(sensors):
        for I,[X,Y] in enumerate(sensors[i+1:],i+1):
            if (X-x)*(X-x) + (Y-y)*(Y-y) <= 4*r*r:
                union(i,I)

    return find(top[0]) != find(bottom[0])

canGoFromLeftToRight(1, [(0,0),(0.5,0.2),(0.7,0.4),(0.6,0.6),(1,1)], 0.5) # False
canGoFromLeftToRight(1, [(0,0),(0.5,0.2),(0.7,0.4),(1,1)], 0.5) # True

- adr September 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Please could you clarify you solution ?

- shivamdurani220 September 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thanks for solution !!

In which company do you work ?

- shivamdurani220 September 16, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Above approach is generally correct but you need to get clarification from the interviewer that there is no case that the series of sensors are trapping the thief as a half circle on the left wall without touching the "top" and "bottom".

As below: (T for thief, s for sensors with range)
+--------------------------
|
|ssssss
| s
|T s
| s
|ssssss
|
+----------------------

- ody September 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

first of all, thanks to 'adr' for sharing such.. i got to know what 'union-find' algo.
actually i'd like to change like following to get same parent correctly after union bottom and top, according to my test.. so in summary, if sensors are all connected, can't pass thru hence return False. if not, return True. again, thanks to adr. i learned one algo.

for i,j in zip(bottom, bottom[1:]):
        union(i,j) -> union(j,i)

if (X-x)*(X-x) + (Y-y)*(Y-y) <= r*r:
        union(i,I) -> union(I,i)

- lee19856 October 26, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

doesn't seem like it needs any fancy union-set structures.

First, create a room of 2d NxN matrix using int.
For each sensor, mark the radius it covers with a special int, like 1 or 2 or whatever in the matrix.
Start at any point on the left that isn't a special int. Recusively visit up, down, right until you reach the right side, or not. Optionally change the matrix cell to another special int like 5 or something to mark the location as being visited. However, if you don't go left at all, I don't think this is necessary.

- dfs November 05, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a graph problem is disguise.

Create a vertex for each lazer. Create a vertex for the top wall and the bottom wall.
Add an edge between lazer vertices if the range of the lazers overlap (ie: the distance between the centers is <= 2*radius.
Add an edge between a wall vertex and a laser vertex if the position of the lazer is within radius from the wall.

Run BFS or DFS from the top wall vertex. If the bottom wall vertex is reachable from the top, then there is a sequence of lasers whose ranges overlap so as to block the thief's path.

For an input with n lazers runtime is O(n^2) with O(n^2) memory.

#include <vector>
#include <iostream>

using namespace std;

struct Lazer {
	double x;
	double y;
};

struct Room {
	double height;
	double width;
	double radius;
	vector<Lazer> lazers;
};

double overlap(const Lazer &a, const Lazer &b, double radius) {
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	double d2 = dx*dx + dy*dy;
	return d2 <= 4*radius*radius;
}

bool canCross(const Room &room) {
	// Create graph
	vector<vector<int>> adjLists(room.lazers.size() + 2);

	// Lazers are verticies
	// Create verticies for top and bottom walls
	int topIndex = (int)room.lazers.size();
	int bottomIndex = topIndex + 1;

	// Edge between verticies if range of lazers overlaps/is tangent
	for(int i = 0; i < (int)room.lazers.size(); ++i) {
		for(int j = 0; j < (int)room.lazers.size(); ++j) {
			if(i == j) continue;
			if(overlap(room.lazers[i], room.lazers[j], room.radius)) {
				adjLists[i].push_back(j);
			}
		}
		// Add edge from lazer vertex to bottom wall if lazers within r of wall
		if(room.lazers[i].y + room.radius >= room.height) {
			adjLists[i].push_back(bottomIndex);
		}
	}

	for(int i = 0; i < (int)room.lazers.size(); ++i) {
		// Add edge from top wall vertex to lazer vertex if lazer within r
		if(room.lazers[i].y <= room.radius) {
			adjLists[topIndex].push_back(i);
		}
	}

	// Run BFS or DFS to see of bottom wall is reachible from top
	vector<bool> discovered(adjLists.size());
	vector<int> stack;
	stack.push_back(topIndex);
	discovered[topIndex] = true;
	while(!stack.empty()) {
		int u = stack.back();
		stack.pop_back();
		for(int v : adjLists[u]) {
			if(discovered[v]) continue;
			// there is a path from top wall to bottom wall completely covered by lazers
			if(v == bottomIndex) return false;
			discovered[v] = true;
			stack.push_back(v);
		}
	}
	return true;
}

struct TestCase {
	Room room;
	bool expected;
};

ostream& operator<<(ostream &os, const Room &room) {
	os << "Room:\n";
	os << " Height: " << room.height << '\n';
	os << " Width: " << room.width << '\n';
	os << " Lazer Radius: " << room.radius << '\n';
	os << " Lazers: ";
	for(auto &l : room.lazers) {
		os << "(" << l.x << " " << l.y << ") ";
	}
	os << endl;
	return os;
}

int main() {
	TestCase testCases[] = {
		{{10, 10, 3.01, {{5, 4}, {5, 8

, true},
{{10, 10, 1.01, {{5, 1}, {5.1, 1.5}, {5.1, 2.5}, {5.2, 3.1}, {5.1, 4.9

- as November 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a graph problem is disguise.

Create a vertex for each lazer. Create a vertex for the top wall and the bottom wall.
Add an edge between lazer vertices if the range of the lazers overlap (ie: the distance between the centers is <= 2*radius.
Add an edge between a wall vertex and a laser vertex if the position of the lazer is within radius from the wall.

Run BFS or DFS from the top wall vertex. If the bottom wall vertex is reachable from the top, then there is a sequence of lasers whose ranges overlap so as to block the thief's path.

For an input with n lazers runtime is O(n^2) with O(n^2) memory.

#include <vector>
#include <iostream>

using namespace std;

struct Lazer {
	double x;
	double y;
};

struct Room {
	double height;
	double width;
	double radius;
	vector<Lazer> lazers;
};

double overlap(const Lazer &a, const Lazer &b, double radius) {
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	double d2 = dx*dx + dy*dy;
	return d2 <= 4*radius*radius;
}

bool canCross(const Room &room) {
	// Create graph
	vector<vector<int>> adjLists(room.lazers.size() + 2);

	// Lazers are verticies
	// Create verticies for top and bottom walls
	int topIndex = (int)room.lazers.size();
	int bottomIndex = topIndex + 1;

	// Edge between verticies if range of lazers overlaps/is tangent
	for(int i = 0; i < (int)room.lazers.size(); ++i) {
		for(int j = 0; j < (int)room.lazers.size(); ++j) {
			if(i == j) continue;
			if(overlap(room.lazers[i], room.lazers[j], room.radius)) {
				adjLists[i].push_back(j);
			}
		}
		// Add edge from lazer vertex to bottom wall if lazers within r of wall
		if(room.lazers[i].y + room.radius >= room.height) {
			adjLists[i].push_back(bottomIndex);
		}
	}

	for(int i = 0; i < (int)room.lazers.size(); ++i) {
		// Add edge from top wall vertex to lazer vertex if lazer within r
		if(room.lazers[i].y <= room.radius) {
			adjLists[topIndex].push_back(i);
		}
	}

	// Run BFS or DFS to see of bottom wall is reachible from top
	vector<bool> discovered(adjLists.size());
	vector<int> stack;
	stack.push_back(topIndex);
	discovered[topIndex] = true;
	while(!stack.empty()) {
		int u = stack.back();
		stack.pop_back();
		for(int v : adjLists[u]) {
			if(discovered[v]) continue;
			// there is a path from top wall to bottom wall completely covered by lazers
			if(v == bottomIndex) return false;
			discovered[v] = true;
			stack.push_back(v);
		}
	}
	return true;
}

struct TestCase {
	Room room;
	bool expected;
};

ostream& operator<<(ostream &os, const Room &room) {
	os << "Room:\n";
	os << " Height: " << room.height << '\n';
	os << " Width: " << room.width << '\n';
	os << " Lazer Radius: " << room.radius << '\n';
	os << " Lazers: ";
	for(auto &l : room.lazers) {
		os << "(" << l.x << " " << l.y << ") ";
	}
	os << endl;
	return os;
}

int main() {
	TestCase testCases[] = {
		{{10, 10, 3.01, {{5, 4}, {5, 8

, true},
{{10, 10, 1.01, {{5, 1}, {5.1, 1.5}, {5.1, 2.5}, {5.2, 3.1}, {5.1, 4.9

- as November 22, 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