Google Interview Question SDE-2s
Country: United States
Interview Type: Phone Interview
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
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
|
+----------------------
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)
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.
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
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
using adr help;
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) {
sensors.add(new Sensors(x, y, r, 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
sensorsCoveringTop.add(s);
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
sensorsCoveringBottom.add(s);
}
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));
}
}
This is a percolation problem solvable using union-find.
- adr September 15, 2018The 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.