## Google Interview Question for SDE-2s

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
4
of 4 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.

Comment hidden because of low score. Click to expand.
2
of 2 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``````

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

Please could you clarify you solution ?

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

Thanks for solution !!

In which company do you work ?

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
|
+----------------------

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

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.

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

bool canCross(const Room &room) {
// Create graph

// 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;
}
}
// Add edge from lazer vertex to bottom wall if lazers within r of wall
if(room.lazers[i].y + room.radius >= room.height) {
}
}

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

// Run BFS or DFS to see of bottom wall is reachible from top
vector<int> stack;
stack.push_back(topIndex);
discovered[topIndex] = true;
while(!stack.empty()) {
int u = stack.back();
stack.pop_back();
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 << " 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

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

bool canCross(const Room &room) {
// Create graph

// 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;
}
}
// Add edge from lazer vertex to bottom wall if lazers within r of wall
if(room.lazers[i].y + room.radius >= room.height) {
}
}

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

// Run BFS or DFS to see of bottom wall is reachible from top
vector<int> stack;
stack.push_back(topIndex);
discovered[topIndex] = true;
while(!stack.empty()) {
int u = stack.back();
stack.pop_back();
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 << " 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

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

``````public class ThiefInRoomOfSensors {

static class Subsets {
int parent;
int rank;

public Subsets(int parent, int rank) {
this.parent = parent;
this.rank = rank;
}

@Override
public String toString() {
return "{" +
"parent=" + parent +
", rank=" + rank +
'}';
}
}

static class GraphUnionFind {
Subsets parent[];

public GraphUnionFind(int nodes) {
parent = new Subsets[nodes + 1]; //since id start from 1

for (int i = 1; i <= nodes; i++) {
parent[i] = new Subsets(i, 1);
}

}

public int find(int i) {
if (parent[i].parent == i)
return i;
return parent[i].parent = find(parent[i].parent);
}

public void union(int i, int j) {

int p1 = find(i);
int p2 = find(j);
if (p1 != p2)
if (parent[p1].rank < parent[p2].rank)
parent[p1].parent = p2;
else if (parent[p1].rank > parent[p2].rank)
parent[p2].parent = p1;
else {
parent[p2].parent = p1;
parent[p1].rank++;
}

}
}

static class Sensors {
int id ;
double x, y;
double r;

public Sensors(double x, double y, double r, int id) {
this.x = x;
this.y = y;
this.r = r;
this.id = id;
}

@Override
public String toString() {
return "{" +
"id=" + id +
", x=" + x +
", y=" + y +
", r=" + r +
'}';
}
}

static class Room {
double height;
double width;

List<Sensors> sensors;

public Room(int s, double h, double w) {
sensors = new ArrayList<>(s);
height = h;
width = w;
}

public void putSensors(double x, double y, double r, int id) {
}
}

public static void main(String args[]) {

Room room = new Room(5, 1, 1);

room.putSensors(0, 0, 0.5, 1);
room.putSensors(0.5, 0.2, 0.5, 2);
room.putSensors(0.7, 0.4, 0.5, 3);
room.putSensors(0.6, 0.6, 0.5, 4);
room.putSensors(1, 1, 0.5, 5);

Room room2 = new Room(3, 1, 1);

room2.putSensors(0, 0, 0.5, 1);
room2.putSensors(0.5, 0.2, 0.5, 2);
room2.putSensors(0.7, 0.4, 0.5, 3);

System.out.println(canGoFromLeftToRight(room));
System.out.println(canGoFromLeftToRight(room2));
}

private static boolean canGoFromLeftToRight(Room room) {
double roomH = room.height;
List<Sensors> sensors = room.sensors;

List<Sensors> sensorsCoveringTop = new ArrayList<>();
List<Sensors> sensorsCoveringBottom = new ArrayList<>();

//Find that overlaps room height
for (int i = 0; i < sensors.size(); i++) {
Sensors s = sensors.get(i);

if (s.y + s.r >= roomH) // overlap top; from the center of the sensors, if we add radius to its height(y) and its beyond or touch room height

if (s.y <= s.r) //overlap bottom; as y is the y-th coordinates, r is radius (as height) ; lets suppose height of room is H; then height of y coordinate is (H-y)
// remaining height is (H-(H-y)= y, hence y<=r then touches
}

if (sensorsCoveringBottom.isEmpty() || sensorsCoveringTop.isEmpty())
//nothing overlaps;
return true;

//means either of them overlap, find the overlaps and combine them
GraphUnionFind graphUnionFind = new GraphUnionFind(sensors.size());

//Combine overlapping top sensors
for (int i = 0; i < sensorsCoveringTop.size() - 1; i++) {
Sensors x = sensorsCoveringTop.get(i);
Sensors y = sensorsCoveringTop.get(i + 1);
graphUnionFind.union(x.id, y.id);
}

//Combine overlapping bottom sensors
for (int i = 0; i < sensorsCoveringBottom.size() - 1; i++) {
Sensors x = sensorsCoveringBottom.get(i);
Sensors y = sensorsCoveringBottom.get(i + 1);
graphUnionFind.union(x.id, y.id);
}

//Combine overlapping top & bottom sensors
for (int i = 0; i < sensors.size(); i++) {
for (int j = i + 1; j < sensors.size(); j++) {

//if they overlap
Sensors x = sensors.get(i);
Sensors y = sensors.get(j);

if ((Math.pow((x.x - y.x), 2) + Math.pow((x.y - y.y), 2)) <= 4 * Math.pow(x.r, 2)) { //x^2 + y^2 <= 4*r^2
graphUnionFind.union(x.id, y.id);
}
}
}
return (graphUnionFind.find(sensorsCoveringTop.get(0).id) != graphUnionFind.find(sensorsCoveringBottom.get(0).id));
}
}``````

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.